7写出二叉树中序遍历的非递归算法
#include typedef struct BiTNode{ char data; int bit; struct BiTNode *lchild,*rchild,*parent;}BiTNode;void InitBT(BiTNode *&t)//1、初始化,不带头结点{ t=NULL;}/*void InitBT(BiTNode *t)//初始化,带头结点{ t=new BiTNode; t->lchild=t->rchild=t->parent=NULL;}*/int EmptyBT(BiTNode *t)//判断队空{ if(t==0) return 1; else ret...全部
#include typedef struct BiTNode{ char data; int bit; struct BiTNode *lchild,*rchild,*parent;}BiTNode;void InitBT(BiTNode *&t)//1、初始化,不带头结点{ t=NULL;}/*void InitBT(BiTNode *t)//初始化,带头结点{ t=new BiTNode; t->lchild=t->rchild=t->parent=NULL;}*/int EmptyBT(BiTNode *t)//判断队空{ if(t==0) return 1; else return 0;}BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树{ BiTNode *p; char ch; cin>>ch; if(ch=='#')return 0; else { p=new BiTNode; p->data=ch; p->parent=t; p->bit=b; t=p; t->lchild=creatBT(t,0); t->rchild=creatBT(t,1); } return t;}void preorder(BiTNode *t)//3、先序遍历{ if(!EmptyBT(t)) { coutdata; preorder(t->lchild); preorder(t->rchild); }}void inorder(BiTNode *t)//中序遍历{ if(!EmptyBT(t)) { inorder(t->lchild); coutdata; inorder(t->rchild); }}void postorder(BiTNode *t)//后序遍历{ if(!EmptyBT(t)) { postorder(t->lchild); postorder(t->rchild); coutdata; }}void coutBT(BiTNode *t,int &m,int &n,int &i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数{ if(!EmptyBT(t)) { if((t->lchild==0) && (t->rchild==0)) m ;//叶子结点 else if((t->lchild!=0) && (t->rchild!=0)) i ;//度为2的结点 else n ;//度为1的结点 coutBT(t->lchild,m,n,i); coutBT(t->rchild,m,n,i); }}void coutNode(BiTNode *t,int &k)//5、求二叉树中结点个数{ if(!EmptyBT(t)) { k ; coutNode(t->lchild,k); coutNode(t->rchild,k); }}int BTdepth(BiTNode *t)//6、求二叉树的深度{ int i,j; if(EmptyBT(t)) return 0; else { i=BTdepth(t->lchild); j=BTdepth(t->rchild); return (i>j?i:j) 1; }}int Xdepth(BiTNode *t,char x)//7、查找x的层数{ int num1,num2,n; if(t==NULL) return 0; else{ if(t->data==x) return 1; num1=Xdepth(t->lchild,x); num2=Xdepth(t->rchild,x); n=num1 num2; if(num1!=0||num2!=0) n ; return n; }} static int flag;void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子{ if(!EmptyBT(t)) { if(k==0) { coutlchild==0) coutlchild->data)rchild==0) coutrchild->data)lchild,k); SearchChild(t->rchild,k); } } }}int Xancestor(BiTNode *t,char x)//9、查找x结点祖先{ int n,num1,num2; if(t==NULL) return 0; else { if(t->data==x) return 1; num1=Xancestor(t->lchild,x); num2=Xancestor(t->rchild,x); n=num1 num2; if(n!=0) { n ; coutdatalchild==0) && (t->rchild==0)) { coutdataparent) coutlchild); BTNodePath(t->rchild); } }}void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码{ if(!EmptyBT(t)) { if((t->lchild==0) && (t->rchild==0)) { coutdataparent!=0;p=p->parent) coutlchild); BTNodebit(t->rchild); } }}void main(){ BiTNode *t; int m,n,i,d,q,k; char x; cout>x; if(Xdepth(t,x)==0) cout>k; SearchChild(t,k); if(k>flag) cout>x; int num; num=Xancestor(t,x); if(num==0) cout if(num==1) coutcout BTNodePath(t); cout BTNodebit(t);}二叉树基本都采用链表存储,顺序存储过时了!你可以把顺序存储转换为链式存储,然后在实现相应算法就是了哈!!。
收起