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;
}
