Page 126 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

} Notes
}
return(p);
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
if(p != NULL)
{
inorder(p->lchild);
printf(“%d\t”,p->data);
inorder(p->rchild);
}
}
void main()
{
struct tnode *root = NULL;
int n,x;
printf(“Enter the number of nodes\n”);
scanf(“%d”,&n);
while( n --- > 0)
{
printf(“Enter the data value\n”);
scanf(“%d”,&x);
root = insert(root,x);
}
inorder(root);
printf(“\nThe number of nodes in tree are :%d\n”,count(root));
}
Input

1. The number of nodes the created tree should have = 5
2. The data values of the nodes in the tree to be created are: 10, 20, 5, 9, 8

Output

1. 5 8 9 10 20
2. The number of nodes in the tree is 5

6.3 Searching for a Target Key in a Binary Search Tree

Searching for the key in the given binary search tree, start with the root node and compare the
key with the data value of the root node. If they match, return the root pointer. If the key is less
than the data value of the root node, repeat the process by using the left subtree. Otherwise,
repeat the same process with the right subtree until either a match is found or the subtree under
consideration becomes an empty tree.

LOVELY PROFESSIONAL UNIVERSITY 121