/* additional functions needed to be added are the following
1. deleting a node in a BT -> BST deletion of a node
2. cntSubtree(tree) -> retrieves the number of subtrees in a BT
3. isParent(node_value) -> returns 1/0 (Yes/No) if node in a BT is a parent node
4. minValue(tree) -> returns the minimum node value in a BT
5. pathLength(tree,node) -> returns the length of the path from root to node
*/
void main() {
int num;
char choice, ans;
//char *str1="world", *str2="world";
struct tnode *p; /* p can be said as the root ptr */
p=NULL;
/* Printing the menu */
//printf("%s < %s is %d", str1, str2, strcmp(str1,str2));
//getch();
do {
clrscr();
printf("PROGRAM TO IMPLEMENT BINARY TREE USING LINKED LIST STRUCTURE");
printf("\n=====================================");
printf("\n1.Insert A Node");
printf("\n2.Size of the Tree");
printf("\n3.Inorder Traversal");
printf("\n4.Preorder Traversal");
printf("\n5.Postorder Traversal");
printf("\n6.Search a Node Value");
printf("\n7.Exit");
switch(choice) {
case '1':
do {
printf("\nEnter any number : ");
scanf("%d",&num);
p=insert(p,num);
printf("Enter more (y/n) :");
fflush(stdin);
ans=getchar();
} while(ans !='n');
break;
case '2':
printf("\nSize of the Tree : %d", size(p));
getch();
break;
case '3':
printf("\nInorder Traversal : ");
inorder(p);
getch();
break;
case '4':
printf("\nPreorder Traversal : ");
preorder(p);
getch();
break;
case '5':
printf("\nPostorder Traversal : ");
postorder(p);
getch();
break;
case '6':
printf("\nLook for a node value : ");
scanf("%d",&num);
if(lookup(p,num))
printf("Node Value Found.");
else
printf("Node Value Not Found.");
getch();
break;
case '7':
printf("\n\nQuiting.......");
getch();
exit(0);
break;
case '8':
printf("\nMaximum Depth : %d", maxDepth(p));
getch();
break;
case 'a':
printf("Minimum Value : %d", minValue(p));
getch();
break;
case 'b':
printf("Maximum Value : %d", maxValue(p));
getch();
break;
default:
gotoxy(1,15);printf("Invalid choice.Please Enter Correct Choice");
getch();
goto oper;
}
} while(choice !=7);
}
struct tnode *insert(struct tnode *node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL)
return NewNode(data);
else {
// 2. Otherwise, recur down the tree
if (data < node->data)
node->lchild = insert(node->lchild, data);
else if (data > node->data)
node->rchild = insert (node->rchild, data);
int lookup(struct tnode *node, int target) {
// 1. Base Case -> Empty Tree
// in that case, the target is not foundso return false
if (node == NULL)
return 0;
else {
// 2. see if found here
if (target == node->data)
return 1;
else {
// 3. otherwise recur down the correct subtree
if (target < node->data)
return lookup(node->lchild, target);
else return lookup(node->rchild, target);
}
}
}