资源描述
p.127 12 (1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF,则可以根据前序序列找到根结点为A,由此,通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点,又由前序序列可知B和C分别为两棵子树的根结点.以此类推可画出所有结点。(2)以同样的方法可画出该二叉树。(3)这两棵不同的二叉树。:p.127 12Hp.127 12(3)这两棵不同的二叉树。:p.127 13p.128 26typedef char DataType;/定义DataType类型typedef struct nodeDataType data;struct node *lchild,*rchild;BinTNode,*BinTree;void CopyTree(BinTree root,BinTree*newroot)就是我们上课经常演示的形式 void CopyTree(BinTNode*root,BinTNode*pnewroot)p.128 26void CopyTree(BinTNode*root,BinTNode *pnewroot)/拷贝二叉树if(root)/如果结点非空 /按前序序列拷贝*pnewroot=new BinTNode;/生成新结点(*pnewroot)-data=root-data;/拷贝结点数据 CopyTree(root-lchild,&(*pnewroot)-lchild);/拷贝左子树 CopyTree(root-rchild,&(*pnewroot)-rchild);/拷贝右子树 else /如果结点为空*pnewroot=NULL;/将结点置空 p.128 27(1)BinTNode *SchBTree(BinTNode*T,DataType x)BinTNode *s100,*p;int top,i;if(!T)return NULL;s0=T;top=1;while(top0)p=s-top;if(p-data=x)return p;if(p-rchild!=NULL)stop+=p-rchild;if(p-lchild!=NULL)stop+=p-lchild;return NULL;p.128 27(2)int InLevel(BinTNode *T,DataType x)BinTNode *q100,*p;int front,rear,k,lev100;if(T=NULL)return -1;/空树 q0=T;lev0=1;front=0;rear=1;while(frontdata=x)return k;if(p-lchild!=NULL)qrear=p-lchild;levrear+=k+1;if(p-rchild!=NULL)qrear=p-rchild;levrear+=k+1;return 0;/x的结点不在树中 p.128 28#define M 100char TM;void Preorder(char *T,int n)int i,j,sM,top=0;if(n=0)return;s0=0;top=1;while(top0)i=s-top;cout Ti;if(2*i+2n)j=2*i+2;stop+=j;/右子结点下标入栈if(2*i+1n)j=2*i+1;stop+=j;/左子结点下标入栈 p.128 29void Levorder(BinTNode *T)BinTNode *q100,*p;int front,rear;if(T=NULL)return;q0=T;front=0;rear=1;while(frontrear)p=qfront+;cout data;if(p-lchild!=NULL)qrear+=p-lchild;if(p-rchild!=NULL)qrear+=p-rchild;
展开阅读全文