erchashu.rar

#include<iostream.h> #include<stdio.h> #include<malloc.h> //#include<string.h> typedef char elemtype; #define Maxsize 50 //#include"btree.h" typedef struct node { elemtype data; struct node *lchild; struct node *rchild; }Btnode; void createBtnode(Btnode *&b,char *str) { Btnode *st[Maxsize]; Btnode *p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while (ch!='\0') { switch(ch) { case '(':top++;st[top]=p;k=1;break; case ')':top--;break; case ',':k=2;break; default : p=(Btnode *)malloc(sizeof(Btnode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:st[top]->lchild=p;break; case 2:st[top]->rchild=p;break; } } } j++; ch=str[j]; } } Btnode *findnode(Btnode *b,elemtype x) { Btnode *p; if(b==NULL) return NULL; else if (b->data==x) return b; else { p=findnode(b->lchild,x); if(p!=NULL) return p; else return findnode(b->rchild,x); } } Btnode *lchildnode(Btnode *p) { return p->lchild; } Btnode *rchildnode(Btnode *p) { return p->rchild; } void child(Btnode *p) { //Btnode *n; if(p!=NULL) { if(p->lchild==NULL && p->rchild==NULL) cout<<p->data; child(p->lchild); child(p->rchild); } } int Btnodeheight(Btnode *b) { int lchildh,rchildh; if(b==NULL) return(0); else { lchildh=Btnodeheight(b->lchild); rchildh=Btnodeheight(b->rchild); return (lchildh>rchildh)? (lchildh+1):(rchildh+1); } } void dispbtnode(Btnode *b) { if (b!=NULL) { printf("%c",b->data); if (b->lchild!=NULL||b->rchild!=NULL) { printf("("); dispbtnode(b->lchild); if(b->rchild!=NULL) printf(","); dispbtnode(b->rchild); printf(")"); } } } void preorder(Btnode *b) { if (b!=NULL) { printf("%c",b->data); preorder(b->lchild); preorder(b->rchild); } } void inorder(Btnode *b) { if (b!=NULL) { inorder(b->lchild); printf("%c",b->data); inorder(b->rchild); } } void postorder(Btnode *b) { if (b!=NULL) { postorder(b->lchild); postorder(b->rchild); printf("%c",b->data); } } void Allpath(Btnode *b) { Btnode *st[50]; Btnode *p; int flag,i,top=-1; if(b!=NULL) { do { while(b!=NULL) { top++; st[top]=b; b=b->lchild; } p=NULL; flag=1; while(top!=-1 && flag) { b=st[top]; if(b->rchild==p) { if(b->lchild==NULL && b->rchild==NULL) { for(i=top;i>0;i--) printf("%c->",st[i]->data); printf("%c\n",st[0]->data);} top--; p=b; } else { b=b->rchild; flag=0; } } }while(top!=-1); cout<<endl; } } int f(Btnode *b) { if(b==NULL) return 0; else return(f(b->lchild)+f(b->rchild)+1); } void main() { char X; Btnode *b,*a1,*a2; //Btnode *p; //char str[20]="A(B(D(G)),C(E,F))"; //cout<<"原来的树:"<<endl<<"A(B(D(G)),C(E,F))"<<endl; cout<<"新建立的树:"<<endl; createBtnode(b,"A(B(D,E(H(J,K(L,M(N))))),C(F,G(I))"); dispbtnode(b); cout<<endl<<"树的高度:"<<Btnodeheight(b)<<endl; cout<<"先根遍历："<<endl; preorder(b);cout<<endl; cout<<"中根遍历："<<endl; inorder(b);cout<<endl; cout<<"后根遍历："<<endl; postorder(b);cout<<endl; cout<<"所有结点的个数："<<f(b)<<endl; cout<<"所有的叶子结点:";child(b);cout<<endl; char a; cout<<"是否查找结点?(y/n)"; cin>>a; while(a!='n') { cout<<"请输入你要查找的结点："; cin>>X; a1=lchildnode(findnode(b,X)),a2=rchildnode(findnode(b,X)); if(a1!=NULL) cout<<"左孩子结点："<<a1- rel='nofollow' onclick='return false;'>data<<endl; else cout<<"没有左孩子结点"<<endl; if(a2!=NULL) cout<<"右孩子结点："<<a2- rel='nofollow' onclick='return false;'>data<<endl; else cout<<"没有左孩子结点"<<endl; } Allpath(b); return; }