70 lines
2.7 KiB
C
70 lines
2.7 KiB
C
|
#include<stdio.h>
|
||
|
|
#include<stdlib.h>
|
||
|
|
#define M 100
|
||
|
|
|
||
|
|
typedef struct N *P;
|
||
|
|
typedef struct N{int d;P l,r;}N;P root;
|
||
|
|
|
||
|
|
int t=-1;P stk[M];
|
||
|
|
P cn(int v){P n=malloc(sizeof(N));n->d=v;n->l=n->r=NULL;return n;}
|
||
|
|
|
||
|
|
void ct(int n){
|
||
|
|
int v,i;char dir[50];P p=NULL,c;
|
||
|
|
for(int k=0;k<n;k++){
|
||
|
|
scanf("%d",&v);P tmp=cn(v);
|
||
|
|
if(!root)root=tmp;
|
||
|
|
else{
|
||
|
|
scanf("%s",dir);c=root;
|
||
|
|
for(i=0;dir[i]&&c;i++){
|
||
|
|
p=c;c=(dir[i]=='L'||dir[i]=='l')?c->l:c->r;
|
||
|
|
}
|
||
|
|
if(c||dir[i]){free(tmp);continue;}
|
||
|
|
(dir[i-1]=='L'||dir[i-1]=='l')?(p->l=tmp):(p->r=tmp);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int e(){return t==-1;}void p(P n){if(t<M-1)stk[++t]=n;}
|
||
|
|
P o(){return e()?NULL:stk[t--];}
|
||
|
|
|
||
|
|
void io(P n){while(1){while(n){p(n);n=n->l;}if(!(n=o()))break;printf("%d ",n->d);n=n->r;}}
|
||
|
|
void po(P n){while(1){while(n){p(n);printf("%d ",n->d);n=n->l;}if(!(n=o()))break;n=n->r;}}
|
||
|
|
void pso(P n){while(1){if(n){p(n);n=n->l;}else{if(e())break;P tmp=stk[t]->r;if(!tmp){tmp=o();printf("%d ",tmp->d);while(!e()&&tmp==stk[t]->r){tmp=o();printf("%d ",tmp->d);}}else n=tmp;}}}
|
||
|
|
|
||
|
|
P pn(P n,int v){if(!n)return NULL;if((n->l&&n->l->d==v)||(n->r&&n->r->d==v))return n;P l=pn(n->l,v);return l?l:pn(n->r,v);}
|
||
|
|
|
||
|
|
int md(P n){if(!n)return 0;int l=md(n->l),r=md(n->r);return(l>r?l:r)+1;}
|
||
|
|
int pa(P n,int v){if(!n)return 0;if(n->d==v)return 1;if(pa(n->l,v)||pa(n->r,v)){printf("%d ",n->d);return 1;}return 0;}
|
||
|
|
void cl(P n,int *c){if(n&&!n->l&&!n->r)(*c)++;if(n){cl(n->l,c);cl(n->r,c);}}
|
||
|
|
|
||
|
|
int main(){
|
||
|
|
int n,ch,v,lc;
|
||
|
|
printf("\nBinary Tree Menu:\n");
|
||
|
|
printf("1. Create Tree\n");
|
||
|
|
printf("2. Inorder Traversal\n");
|
||
|
|
printf("3. Preorder Traversal\n");
|
||
|
|
printf("4. Postorder Traversal\n");
|
||
|
|
printf("5. Find Parent of Node\n");
|
||
|
|
printf("6. Find Max Depth\n");
|
||
|
|
printf("7. Print Ancestors of Node\n");
|
||
|
|
printf("8. Count Leaf Nodes\n");
|
||
|
|
printf("9. Exit\n");
|
||
|
|
do{
|
||
|
|
printf("Enter choice: ");
|
||
|
|
scanf("%d",&ch);
|
||
|
|
switch(ch){
|
||
|
|
case 1:printf("Enter number of nodes: ");scanf("%d",&n);ct(n);break;
|
||
|
|
case 2:printf("Inorder: ");io(root);puts("");break;
|
||
|
|
case 3:printf("Preorder: ");po(root);puts("");break;
|
||
|
|
case 4:printf("Postorder: ");pso(root);puts("");break;
|
||
|
|
case 5:printf("Enter value to find parent: ");scanf("%d",&v);P p=pn(root,v);p?printf("Parent: %d\n",p->d):puts("Node not found");break;
|
||
|
|
case 6:printf("Max Depth: %d\n",md(root));break;
|
||
|
|
case 7:printf("Enter value to find ancestors: ");scanf("%d",&v);pa(root,v)?puts(""):puts("No ancestors found");break;
|
||
|
|
case 8:lc=0;cl(root,&lc);printf("Leaf count: %d\n",lc);break;
|
||
|
|
case 9:break;
|
||
|
|
default:puts("Invalid choice");
|
||
|
|
}
|
||
|
|
}while(ch!=9);
|
||
|
|
return 0;
|
||
|
|
}
|