第九章 遍历 树的恢复 new.ppt

二叉树的广度优先遍历 二叉树的广度优先遍历又称为按层次遍历，这种遍历方式是先遍历二叉树的第一层结点，然后遍历第二层结点，……最后遍历最下层的结点。而对每一层的遍历是按从左至右的方式进行。 二叉树的广度优先遍历 按照广度优先遍历方式，在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队，然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。 二叉树的广度优先遍历算法 bitree *Q[maxsize]; void Layer (bitree *p) { bitree *s; if ( p!=NULL ) { rear=1; front=0; Q[rear]=p; 二叉树的广度优先遍历算法 while ( frontrear ) { front ++; s=Q[front]; printf (“ %c ” , s→data); if ( s→lchild!=NULL) { rear++; Q[rear]=s→lchild; } if (s→rchild!=NULL) { rear++; Q[rear]=s→rchild; } } } return; } 二叉树的深度优先遍历的非递归算法基本思想 当p所指的结点非空时，将该结点的存储地址进栈，然后再将p指向该结点的左孩子结点； 当p所指的结点为空时，从栈顶退出栈顶元素送p，并访问该结点，然后再将p指向该结点的右孩子结点； 如此反复，直到p为空并且栈空为止。 非递归算法 void ninorder(bitree *T) { SqStack *S; bitree *P=T; InitStack(S); //顺序栈初始化 while( P!=NULL || !Empty(S)) { if (P!=NULL) { Push(S,P); //根结点入栈 P=P-lchild; // 遍历左子树 } else { Pop(S,P); //左子树遍历结束，出栈 printf(%c,P-data); //访问根结点 P=P-rchild; //遍历右子树 } } } 从遍历序列恢复二叉树 利用先序序列确定根节点，在中序序列确定左子树的中序序列和左子树的中序序列。 根据左子树的结点的数目在先序序列中确定左子树的先序序列；同样得到右子树的先序序列。 如此反复，直到取尽先序序列中的结点时，便得到一棵二叉树。 从遍历序列恢复二叉树实例 先序序列为A, B, D, G, C, E, F, H， 中序序列为D, G, B, A, E, C, H, F A是二叉树的根结点，再根据A在中序序列中的位置，可知结点DGB在A的左子树上和ECHF在A的右子树上； 根据先序序列确定B和C分别是A的左子树和右子树的根，再根据B和C在DGB和ECHF中的位置，可知DG在B的左子树上和B的右子树为空以及C的左子树仅有结点E和C的右子树包含结点HF； 遍历序列恢复二叉树算法思想 先将先序和中序序列分别存在两个数组perod[n]和inod[n]中 取先序序列的第一个元素建立整个树的根结点，并利用中序序列确定根结点的左、右子树结点在先序序列中的位置。 接着再用先序序列和中序序列分别对左子树和右子树进行构造。 遍历序列恢复二叉树算法 { int m; bitree *p;p = malloc (sizeof(bitree)); p→data=preod[i]; m=k; while ( inod[m] != preod[i] ) m++; if ( m= =k ) p→lchild = NULL; else p→lchild = BPI( preod, inod, i+1, i+m-k, k, m-1 );