Threaded Binary Tree(TBT)
C Program For Threaded Binary Tree(TBT) Source Code: #include<stdio.h> #include<conio.h> #include<stdlib.h> struct tree { char data; int lt,rt; struct tree *lchild; struct tree *rchild; }; struct tree * s[30]; int top=-1; struct tree * gettree() { struct tree *t; t=(struct tree *)malloc(sizeof(struct tree)); t->lchild=NULL; t->rchild=NULL; t->lt=0; t->rt=0; return t; } struct tree * thread_parent(struct tree * ptr) { struct tree *v,*p,*parent; v=ptr; while(v->rt==0) { v=v->rchild; } p=v->rchild; if(p->lchild==ptr) { parent=p; } else { p=p->lchild; while(p->lchild!=ptr) { p=p->rchild; } parent=p; } return parent; } struct tree * search(struct tree *root,char key) { struct tree *r; if(root==NULL) return NULL; else { if(root->data==key) return root; else { r=search(root->lchild,key); if(r==NULL) { r=search(root->rchild,key); } return r; } } } struct tree * Inoredr_successor(struct tree * ptr) { struct tree *s; s=ptr->rchild; if(ptr->rt==0) { while(s->lt!=1) { s=s->lchild; } } return s; } struct tree * Inorder_predecessor(struct tree * ptr) { struct tree *s; s=ptr->lchild; if(ptr->lt==0) { while(s->rt!=1) { s=s->rchild; } } return s; } void threaded_in_trav(struct tree * header) { struct tree *ptr; ptr=header; while(1) { ptr=Inorder_successor(ptr); if(ptr!=header) printf(" %c",ptr->data); else return; } } void insertion(char x,char n,struct tree *header) { struct tree *ptr,*lptr,*rptr,*nptr,*s; int flag; ptr=Inorder_successor(header); flag=0; while(ptr!=header && flag=1) { if(ptr->data==x) flag=1; else ptr=Inorder_successor(ptr); } if(flag==0) { printf("\n X not found."); return; } else { nptr=gettree(); nptr->data=n; if(opt==1) { if(ptr->lt==1) { nptr->lchild=ptr->lchild; nptr->lt=1; ptr->lt=0; ptr->lchild=nptr; nptr->rchild=ptr; nptr->rt=1; } else { lptr=ptr->lchild; s=Inorder_predecessor(ptr); nptr->rchild=ptr; nptr->rt=1; ptr->lchild=nptr; nptr->lchild=lptr; s->rchild=nptr; } } else if(opt==2) { if(ptr->rt==1) { nptr->rchild=ptr->rchild; nptr->rt=1; ptr->rt=0; ptr->rchild=nptr; nptr->lchild=ptr; nptr->lt=1; } else { rptr=ptr->rchild; s=Inorder_successor(ptr); nptr->lchild=ptr; nptr->lt=1; ptr->rchild=nptr; nptr->rchild=rptr; s->lchild=nptr; } } } } void thread_inorder_deletion(char key,struct tree * header) { struct tree *ptr,*s,*par,*c; char item; ptr=search(header,key); if(ptr->lt==1 && ptr->rt==1) case=1; else if(ptr->lt==0 && ptr->rt==0) case=3; else case=2; par=thread_parent(ptr); if(case==1) { if(par->rchild==ptr) { par->rchild=ptr->rchild; par->rt=1; } else if(par->lchild==ptr) { par->lchild=ptr->lchild; par->lt=1; } } else if(csae==2) { if(ptr->rt==0) c=ptr->rchild; else if(ptr->lt==0) c=ptr->lchild; if(par->lchild==ptr) par->rchild=c; else if(par->lchild==c) par->lchild=c; if(ptr->rt=0) { s=Inoredr_successor(ptr); s->lchild=ptr->lchild; } if(ptr->lt=0) { s=Inored_predecessor(ptr); s->lchild=ptr->lchild; } else if(case==3) { s=Inorder_successor(ptr); item=s->data; thread_inoredr_deletion(header,s->data); ptr->data=item; } } void main() { int ch,h,c,opt,h1,h2,c1,c2; char key,item; float v; struct tree *root,*s,*rt; root=gettree(); root->data='$'; while(1) { printf("\n\nThreaded Binary tree Operations:"); printf("\n\t1.Insertion\n\t2.Deletion\n\t3.Traversal\n\t4.Search\n\t5.Exit"); printf("\n\nEnter your choice:"); scanf("%d",&ch); switch(ch) { case 1: if(root->data=='$') { printf("\nEnter value of the root node:"); fflush(stdin); scanf("%c",&item); } else { printf("\nEnter key:"); fflush(stdin); scanf("%c",&key); printf("\nEnter data:"); fflush(stdin); scanf("%c",&item); } printf("\nEnter as a 1.left-child 2.right-child"); printf("\nEnter your choice:"); fflush(stdin); scanf("%d",&ch); switch(ch) { case 1: opt=1; insertion(root,key,item,opt); break; case 2: opt=2; insertion(root,key,item,opt); break; } break; case 2: if(root->data=='$') printf("\nTree not created."); else { printf("\nEnter the Key:"); fflush(stdin); scanf("%c",&key); deleteleaf(root,key); } break; case 3: printf("\n\n\t1.Inorder\n\t2.Preorder\n\t3.Postorder"); printf("\nEnter Your choice:"); scanf("%d",&ch); switch(ch) { case 1: printf("\nInorder traversal:\n"); inorder(root); break; case 2: printf("\nPreorder traversal:\n"); preorder(root); break; case 3: printf("\nPostorder traversal:\n"); postorder(root); break; } break; case 4: if(root->data=='$') printf("\nTree not created."); else { printf("\nEnter the key:"); fflush(stdin); scanf("%c",&key); s=search(root,key); if(s!=NULL) printf("\nKey found"); else printf("\nKey not found."); } break; case 5: if(root->data=='$') printf("\nTree not created."); else { h=height(root); printf("\nHeight of the binary tree=%d",h); } break; case 6: if(root->data=='$') printf("\nTree not created."); else { c=count(root); printf("\nTotal node of the binary tree=%d",c); } break; case 7: if(root->data=='$') printf("\nTree not created"); else { printf("\nNode-number ??? 1.Left-subtree 2.Right-subtree"); printf("\nEnter your choice:"); scanf("%d",&ch); switch(ch) { case 1: opt=1; h1=nodenum(root,opt)-1; printf("\nNode-number of Left subtree=%d",h1); break; case 2: opt=2; h2=nodenum(root,opt)-1; printf("\nNode-number of Right subtree=%d",h2); break; } } break; case 8: if(root->data=='$') printf("\nTree not created."); else if(root->lchild==NULL && root->rchild==NULL && root->data!=-1) printf("\nOnly the root node is present."); else { c1=1; h1=nodenum(root,c1)-1; c2=2; h2=nodenum(root,c2)-1; if(h1>h2) printf("\nLeft subtree is heavier."); else if(h1<h2) printf("\nRight subtree is heavier."); else printf("\nLeft subtree and Right subtree is of same weight."); } break; case 9: printf("\nTraversal using stack"); printf("\n\t1.Preorder\n\t2.Inorder\n\t3.Postorder"); printf("\nEnter your choice:"); scanf("%d",&ch); switch(ch) { case 1: pre_order(root); break; case 2: in_order(root); break; } break; case 10: exit(0); } } }
Tags:
Tree
0 comments