6.3二叉树的遍历深入学习资料

6.3.1二叉树遍历的非递归算法1.先序遍历的非递归算法2.中序遍历的非递归算法3.后序遍历的非递归算法1.先序遍历的非递归算法(1)二叉树的根结点进栈。(2)当栈不空循环：当栈顶元素非空时访问它，并将该结点的左子树的根结点进栈，直到栈顶元素为空，并将空指针出栈；如果栈不空，栈顶元素出栈，并将该结点的右子树的根结点进栈。如此操作，直到栈空为止。voidPreOrder_Nonrecursive(BiTreeT){//先序遍历的非递归算法InitStack(S);Push(S,T);//根指针进栈while(!StackEmpty(S)){while(GetTop(S)){printf(%c,GetTop(S)-data);//访问结点，向左一步Push(S,GetTop(S)-lchild);}//向左走到尽头Pop(S,p);//空指针出栈if(!StackEmpty(S)){Pop(S,p);Push(S,p-rchild);}//向右一步}//while}//PreOrder_Nonrecursive2.中序遍历的非递归算法(1)二叉树的根结点进栈。(2)当栈不空循环：当栈顶元素非空时，将该结点的左子树的根结点进栈，直到栈顶元素为空，并将空指针出栈；如果栈不空，栈顶元素出栈，访问该元素，并将该结点的右子树的根结点进栈。如此操作，直到栈空为止。voidInOrder_Nonrecursive(BiTreeT){//中序遍历的非递归算法InitStack(S);Push(S,T);//根指针进栈while(!StackEmpty(S)){while(GetTop(S))Push(S,GetTop(S)-lchild);//向左走到尽头Pop(S,p);//空指针出栈if(!StackEmpty(S)){//访问结点，向右一步Pop(S,p);printf(%c,p-data);Push(S,p-rchild);}//if}//while}//InOrder_Nonrecursive3.后序遍历的非递归算法与先序遍历和中序遍历的非递归情况有所不同，在后序遍历二叉树的过程中，对一个结点访问之前，要两次经过这个结点，第一次是由该结点找到其左子树，对其左子树进行遍历，遍历完成后，返回到该结点。第二次是由该结点找到其右子树，对其右子树进行遍历，遍历完成后，返回该结点，此时才能访问该结点。所以，在后序遍历的非递归算法中，同样需要一个栈，而且为了区分某一个结点是第一次进栈还是第二次进栈，在栈结构中还得设置一个标志域来区分。其栈结点的定义如下：typedefstructPMType{BiTreeptr;intmark;//mark=0表示刚刚访问此结点，mark=1表示左子树处理结束返回，mark=2表示右子树处理结束返回。}PMType;6.3.2层次遍历算法层次遍历过程是：将根结点入队，在队列非空时循环：从队列中取出一个元素访问它；若它有左孩子结点，将左孩子结点入队；若它有右孩子结点，将右孩子结点入队。如此操作，直到队列空为止。voidLayerOrder(BiTreeT){//层序遍历二叉树InitQueue(Q);//队列初始化EnQueue(Q,T);//根结点入队while(!QueueEmpty(Q)){DeQueue(Q,p);printf(,p-data);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);}}//LayerOrder4、查询二叉树中某个结点6.3.3遍历算法应用举例1、统计二叉树中叶子结点的个数2、求二叉树的深度3、复制二叉树5、建立二叉树的存储结构1、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增1。voidCountLeaf(BiTreeT,int&count){if(T){if((!T-lchild)&&(!T-rchild))count++;//对叶子结点计数CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);}//if}//CountLeaf2、求二叉树的深度算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、右子树深度的最大值，然后加1。首先分析二叉树的深度和它的左、右子树深度之间的关系。(后序遍历)intDepth(BiTreeT){//返回二叉树的深度if(!T)depthval=0;else{depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);}returndepthval;}3、复制二叉树其基本操作为:生成一个结点。根元素T左子树右子树根元素NEWT左子树右子树左子树右子树(后序遍历)BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){if(!(T=newBiTNode))exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;returnT;}生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode*CopyTree(BiTNode*T){if(!T)returnNULL;if(T-lchild)newlptr=CopyTree(T-lchild);//复制左子树elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);//复制右子树elsenewrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);returnnewT;}//CopyTreeABCDEFGHK^D^C^^H^^K^GA例如:下列二叉树的复制过程如下:newTF^^BE^4、查询二叉树的某个结点算法基本思想:(1)在二叉树不空的前提下，和根结点的元素进行比较，若相等，则找到，返回TRUE；(2)否则在左子树中进行查找，若找到，则返回TRUE；(3)否则继续在右子树中进行查找，若找到，则返回TRUE，否则返回FALSE。intPreorder(BiTreeT,ElemTypex,BiTree&p){//若二叉树中存在和x相同的元素，则p指向该结点并返回OK,//否则p=NULL且返回FALSE}if(T){if(T-data==x){p=T;returnOK,}}//ifelse{p=NULL;returnFALSE;}else{if(Preorder(T-lchild,x,p))returnOK;}//elseelsereturn(Preorder(T-rchild,x,p));5、建立二叉树的存储结构可以在遍历过程中生成结点，建立二叉树的存储结构。下面给出的算法是按先序序列建立二叉树的二叉链表的过程。对图6-5(1)所示二叉树，按下列顺序读入字符AB#C##D#EF##(#为空格字符)可建立相应的二叉链表。intCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T-data=ch;//生成根结点CreateBiTree(T-lchild);//构造左子树CreateBiTree(T-rchild);//构造右子树}returnOK;}//CreateBiTree6.3.4二叉树的构造假设二叉树中每个结点的值均不相同(下面的算法均基于这种假设)，同一颗二叉树具有惟一的先序序列、中序序列和后序序列，但不同的二叉树可能具有相同的先序序列、中序序列和后序序列。ABCABCABCBABCCA图6-8先序序列为ABC的5棵二叉树CABBACABCCACABB图6-9中序序列为ACB的5棵二叉树ACBABCABCBABCCA图6-10后序序列为CBA的5棵二叉树利用数学归纳法可以证明以下两个结论是成立的：(1)任何n(n≥0)个不同结点的二叉树，都可由它的先序序列和中序序列惟一地确定；(2)任何n(n0)个不同结点的二叉树，都可由它的中序序列和后序序列惟一地确定。仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树如果同时已知二叉树的中序序列“cbdaegf”,则会如何？二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列BiTreeBuild_T1(Build_T1(char*Pre,char*In,intn){//先序序列和中序序列已分别存在数组Pre和In中，n为二叉树的结点数，由先序序列和中序序列建立其二叉链表if(n=0)returnNULL;sroot=newBiTNode;sroot-data=*Pre;//建根结点for(p=IN;pIn+n;p++)//在In中查找等于*Pre的位置if(*p==*pre)break//在In中找到后退出循环k=p-In;//确定根结点在In中的位置sroot-lchild=Build_T1(Pre+1,In,k);//递归地建左子树sroot-rchild=Build_T1(Pre+k+1,P+1,n-k-1);//递归地建右子树returnsroot;//返回根指针}//Build_T1