Difference between revisions of "Lecture27ECE264Spring2012" - Rhea

Revision as of 17:18, 23 April 2012

Hanye Xu April 20 Lecture 27

264 exam outcome 1.file 2.structure 3.dynamic structure (linked list)

binary search tree

typedef struct treenode { struct treenode *left; struct treenode *right; int value; }Node;

int Tree_search(Node *n, int v) { /*return 0 if not found,1 if found*/ if(n == NULL){return 0;} if((n->value)==v){return 1;} if((n->value)>v) { return Tree_search(n->left,v); } return Tree_search(n->right,v); }

void Tree_destroy(Node *n) { if(n == NULL){return;} Tree_destroy(n->left); Tree_destroy(n->right); free(n); }

void Tree_print(Node *n) { if(n==NULL){return;} (1)printf("%d",n->value); 1 2 3 -> preorder 6 2 0 4 9 7 (2)Tree_print(n->left); 2 1 3 -> inorder sorting 0 2 4 6 7 9 (3)Tree_print(n->right); 2 3 1 -> postorder 0 4 2 7 9 6 }

Node *Node_construct(int v) { Node *n; n = malloc(sizeof(Node)); n->value = v; n->left = NULL; n->right = NULL; return n; }

Node *Tree_construct(Node *n, int v) { if(n==NULL){return Node_construct(v);} if((n->value)==v){return n;} if((n->value)>v) { n->left = Node_construct(n->left,v); } else { n->right= Node_construct(n->right,v); } return n; }

insert 6,2,4,0,9,7 Node *n =NULL; n=Tree_insert(n,6);

n-> 6 (root) / \

      GRD

n=Tree_insert(n,2);

n-> 6 / \ 2 GRD

       /  \
      GRD

n=Tree_insert(n,4)

n-> 6

       /    \
    2      GRD
   /   \

GRD 4 / \ GRD

Finally n-> 6

                     /    \
                  2      9
                /   \     /  \
              0     4 7   GRD

parser

int y = 3+2; int t = 3 + "ece";

James Chen Notes

Binary search tree

A binary search tree has an initial root and left and right subtrees. Each subtree starts with a node and has left and right children It is possible that the left or right may be NULL if a node has a value v: everything in the left subtree < v everything in the right subtree > v

notes: insert 6, 2, 4 Node *n = NULL;

n=Tree_insert(n, 6);//creates root of 6, its left and right subtrees are NULL

n=Tree_insert(n, 2);

//creates node with value 2, since it is < 6 and the left child of 6 is NULL, 2 becomes the left child

n=Tree_insert(n,4);

//value 4, it is <6 but, the left child is not NULL, the insert function is called using the left child (2). Since 4 > 2, and the right child of 2 is NULL, 4 becomes the right child

each search checks value against node value, and moves left and right as appropriate binary search tree works best when balanced

typedef struct treenode

{

struct treenode *left;

struct treenode *right;

int value;

}Node;

int Tree_search(Node* n, int v) // or Node* Tree_search, returns n or NULL

{

/*return 0 if not found, 1 if found */

if (n==NULL) {return 0;}

if ((n->value) == v) {return 1;}

if ((n->value) > v)

{

return Tree_search(n->left,v);

}

return Tree_search(n->right,v);

}

void Tree_destroy(Node *n)

{

if(n==NULL)

{return;}

Tree_destroy(n->left); // destroy left child

Tree_destroy(n->right); // destroy right child

free(n); // destroy itself

}

void Tree_print(Node *n) // prints least to greatest

{

if(n==NULL)

{return;}

printf(“%d”,n->value); // (1)

Tree_print(n->left);// (2)

Tree_print(n->right);// (3) }

/*

sample tree;

6 2 9 0 4 7

1, 2, 3 → preorder

2, 1, 3 → in order // prints tree in order of least to greatest ( 0 2 4 6 7 9 )

3, 1, 2 → for greatest to least ( 9 7 6 4 2 0 )

2, 3, 1 → post order (hierarchy operation; like PEMDAS)

parser → the very first thing a compiler does. Analyze source code, breaks into smaller units, decides if the units can be put together

• /

Node* Node_construct(int v)

{

Node *n;

n=malloc(sizeof(Node));

n->value = v;

n->left = NULL;

n->right = NULL;

return n; }

Node *Tree_construct(Node *n, int v) {

if(n==NULL)

{

return Node_construct(v);}

}

if((n->value) == v)

{

return n;

}

if((n->value)>n)

{

n->left = Node_construct(n->left,n);

}

else

{

n->right = Node_construct(n->right, v);

}

return n;

}

===================

Kevin Tan(0023987592), section#2 notes 04/19

binary search tree

typedef struct treenode {

 struct treenode *left;
 struct treenode *right;
 int value;

}Node;

int tree_search(Node *n, int v) {

 if (n == NULL) {
   return 0;
 }
 if ((n->value == v)) {
   return 1;
 }
 if (n->value>v) {
   return tree_search(n->left, v);
 }
 return tree_search(n->right, v);

}

void tree_destory(Node *n) {

 if (n==NULL) {
   return;
 }
 tree_destory(n->left);
 tree_destory(n->right);
 free(n);

}

void tree_print(Node *n) {

 if(n==NULL){return 1;}
 printf("%d",n->value);
 tree_print(n->left);
 tree_print(n->right);

}

Node* Node_construct(int v) {

 Node *n;
 n=malloc(sizeof(Node));
 n->value = v;
 n->left = NULL;
 n->right = NULL;  
 return n; }

Node *Tree_construct(Node *n, int v) {

 if(n==NULL)
 {
   return Node_construct(v);}

} if((n->value) == v) {

 return n;

} if((n->value)>n) {

 n->left = Node_construct(n->left,n);

} else {

 n->right = Node_construct(n->right, v);

} return n; }

___________________________________________

Shiyu Wang Lec27 April 22nd

binary search tree typedef struct tree node {

 struct tree node*left;
 struct tree node*right;
 int value;

}Node;

Node * tree_search(Node *n, int v) {

 /*return 0 if not found,1 if found */
 if (n==NULL)
 {
   return NULL;
 }
 if((n->value)==v)
 {
   return n;
 }
 if((n->value)>v)
 {
   return tree_search(n->left, v);
 }
 return tree_search(n->right,v);

}

Void tree_destory(Node*n) {

 if(n==NULL)
 {
   return n;
 }
 tree_destory(n->left);
 tree_destory(n->right);
 free(n);

}

Void Tree_print(node*n) {

 if(n== NULL)
 {
   return ;
 }
 printf("%d", n->value);
 Tree_print(n->left);
 Tree_print(n->right);

}

Node *node_construct(int v) {

 Node *n;
 n=malloc(sizeof(Node));
 n->value=v;
 n->left=NULL;
 n->right = NULL;
 return n;

}

Node *Tree_construct(Node *n, int v) {

 if(n==NULL)
 {
   return Node_construct(v);
 }
 if((n->value)==v)
 {
   return n;
 }
 if((n->value)>v)
 {
   n->left=Node_construct(tree->left,v);
 }
 else
 {
   n->right=Node_construct(tree->right, v);
 }
 return n;

}

=============================

Wudi Zhou Lecture 27, Prof Lu's section, April 23

Topic: Binary search tree.

typedef struct tree node {

 struct treenode * left;
 struct treenode * right;
 int value;

}Node;

Node * tree_search(Node *n, int v) { /*return 0 if not found,1 if found */

 if (n == NULL)
 {
   return NULL;
 }
 if((n -> value)== v)
 {
   return n;
 }
 if((n -> value)> v)
 {
   return tree_search(n -> left, v);
 }
 return tree_search(n -> right, v);

}

void tree_destory(Node*n) {

 if(n == NULL)
 {
   return n;
 }
 tree_destory(n -> left);
 tree_destory(n -> right);
 free(n);

}

void Tree_print(node*n) {

 if( n== NULL)
 {
   return ;
 }
 printf("%d", n->value);
 Tree_print(n->left);
 Tree_print(n->right);

}

Node *node_construct(int v) {

 Node *n;
 n=malloc(sizeof(Node));
 n->value=v;
 n->left=NULL;
 n->right = NULL;
 return n;

}

Node *Tree_construct(Node *n, int v) {

 if(n==NULL)
 {
   return Node_construct(v);
 }
 if((n->value)==v)
 {
   return n;
 }
 if((n->value)>v)
 {
   n->left=Node_construct(tree -> left,v);
 }
 else
 {
   n->right=Node_construct(tree -> right, v);
 }
 return n;

}

Post order: first right Node Pre order: Node left right