数据结构二叉树的遍历及其他操作

第六章

二叉树的遍历及应用本讲内容6.3遍历二叉树1.遍历二叉树的概念2.遍历算法实现（递归算法和非递归算法）先序、中序、后序和层次遍历3.遍历算法的应用举例遍历二叉树遍历二叉树的概念遍历二叉树就是如何按某条搜索路径巡访二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

如何确定搜索路径？先上后下搜索先左后右搜索先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法先左后右的遍历算法先序遍历二叉树遍历策略若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。ABCDEGHFABDEGCFH

递归算法先序遍历二叉树的递归算法实现void

PreOrder(BiTreeT){if(T){ //如果树不为空 visit(T->data

);//输出根结点

PreOrder(T->lchild);//先序遍历左子树

PreOrder

(T->rchild);//先序遍历右子树}}中序遍历二叉树遍历策略若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。ABCDEGHFDBGEAFHC递归算法中序遍历二叉树的递归算法实现void

InOrder(BiTreeT){if(T){ //如果树不为空

InOrder(T->lchild);//中序遍历左子树 visit(T->data

);//输出根结点

InOrder

(T->rchild);//中序遍历右子树}}后序遍历二叉树遍历策略若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。ABCDEGHFDGEBHFCA递归算法后序遍历二叉树的递归算法实现void

PastOrder(BiTreeT){if(T){ //如果树不为空

PastOrder(T->lchild);//后序遍历左子树

PastOrder

(T->rchild);//后序遍历右子树 visit(T->data

);//输出根结点}}层次遍历二叉树遍历策略采用“自上而下，自左而右”的方法访问二叉树中的所有结点，即从第一层开始，依次访问二叉树中每一层的结点，同一层中按照先访问左孩子再访问右孩子的顺序访问结点，直到所有的结点均被访问，此种遍历需要借助于队列来完。ABCDEGHFABCDEFGH层次遍历二叉树的非递归算法实现voidLevelOrder(BinTreeT){ InitQueue(Q); //队列初始化为空

EnQueue

(Q,T); //根入队列

while(!QueueEmpty(Q)){

//队列不空则继续遍历

DeQueue(Q,p);

if(p!=NULL){

visit(p->data);

EnQueue(Q,p->lchild);//左孩子入队列

EnQueue(Q,p->rchild);//右孩子入队列

}

}}首先将根入队列，以后若队列不空则出队头元素p，如果p不空，则访问之。然后将其左右孩子入队列，如此循环直到队列为空。

遍历算法的应用举例1.统计二叉树中叶子结点的个数2.统计二叉树中总结点的个数3.求二叉树的深度4.建立二叉树的存储结构5.交换二叉树的左右子树6.根据遍历序列画对应二叉树统计二叉树中叶子结点的个数算法思想分别求出左子树、右子树的叶子数，然后相加。根据二叉树的五种基本形态知：空二叉树，叶子结点数为0；

只有根的二叉树，叶子结点数为1；

只有左子树的二叉树，叶子结点数为左子树中叶子结点数；只有右子树的二叉树，叶子结点数为右子树中叶子结点数；具有左右子树的二叉树，叶子结点数等于左子树中叶子结点数、右子树中的叶子结点数之和。递归算法实现int

CountLeaf(BiTreeT){

if(!T) return0;

elseif((!T->lchild)&&(!T->rchild))

return

1;

else{

nl=CountLeaf(T->lchild); nr=CountLeaf(T->rchild);

returnnl+nr;

}//if}//CountLeaf空树只有根左子树右子树统计二叉树中总结点的个数算法思想分别求出左子树、右子树的总结点数，然后与根求和。根据二叉树的五种基本形态知：空二叉树，结点数为0；

只有根的二叉树，结点数为1；

只有左子树的二叉树，结点数为左子树中结点数加上根；只有右子树的二叉树，结点数为右子树中结点数加上根；具有左右子树的二叉树，结点数等于左子树中结点数、右子树中的结点数加上根之和。递归算法实现int

NodeCount(BinTreeT){

if(!T) return

0;

else{

nl=

NodeCount(T->lchild); nr=NodeCount(T->rchild); return

1+nl+nr;

}//if}空树左子树右子树求二叉树的深度算法思想二叉树的深度应为其左、右子树深度的最大值加1。根据二叉树的五种基本形态知：空二叉树，深度为0；

只有根的二叉树，深度为1；

只有左子树的二叉树，深度为左子树的深度加1；只有右子树的二叉树，深度为右子树的深度加1；具有左右子树的二叉树，深度等于左子树的深度与右子树的深度的最大值加1。递归算法实现int

Depth(BinTreeT){

if(!T) return

0;

else{

dl=

Depth(T->lchild); dr=Depth(T->rchild);

depth=1+(dl>dr?dl:dr);

}

return

depth;}空树左子树右子树建立二叉树的存储结构二叉树针对不同的定义形式对应不同的建立存储结构的方法。以字符串的形式，按照先序遍历思想，建立一棵二叉树的二叉链表。以空白字符“”表示1.空树2.只含一个根结点的二叉树A以字符串“A”表示ABCDA(B(

,C(

,

)),D(

,

))以下列字符串表示递归算法实现voidCreateBiTree(BiTree&T){ scanf(“%c”,&ch);

if(ch==‘’)T=NULL;

else{

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

exit(overflow);

T->data=ch;//生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树

}}//CreateBiTreeAB

C

D

ABCD算法执行过程举例如下：ATBCD^^^^^交换二叉树的左右子树空树不需要进行任何交换操作；只有根的二叉树交换后仍然只有根；只有左子树的二叉树，交换后变成只有右子树的二叉树；只有右子树的二叉树，交换后变成只有左子树的二叉树；具有左右子树的二叉树交换后，原左子树变成右子树，原右子树变成左子树。分别对于交换后的左子树或右子树重复进行上述操作直到操作完成。算法思想递归算法实现voidchange(BinTree&T){

if(!T)returnT;

else{ t=T->lchild; T->lchild=T->rchild; T->rchild=t;

change(T->lchild); change(T->rchild);

}}

仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，1.由先序和中序遍历序列建立二叉树

如果同时已知二叉树的中序序列“cbdaegf”，则会如何？

二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根主要思想：先序序列中第一个为“根”，标出之；在中序序列中标出“根”，并分出左、右子树；在先序序列中标出左、右子树；分别对左、右子树重复以上步骤。abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列2.由后序和中序遍历序列建立二叉树二叉树的后序序列二叉树的中序序列左子树右子树根左子树右子树根主要思想：后序序列中第一个为“根”，标出之；在中序序列中标出“根”，并分出左、右子树；在后序序列中标出左、右子树；分别对左、右子树重复以上步骤。3.由后序和先序序列能否建立二叉树？二叉树的后序序列二叉树的先序序列左子树右子树根左子树右子树根结论：不能唯一确定二叉树！ABAB或例如：先序：AB后序：BA二叉树遍历的非递归算法遍历二叉树的非递归算法，一般借助于栈实现。仿照递归算法执行过程中递归工作栈的状态变化状况可直接写出相应的非递归算法。先序遍历非递归算法中序遍历非递归算法后序遍历非递归算法先序遍历的非递归算法实现思想首先，根结点先入栈。在栈不空的情况下出栈，若结点存在则访问结点，对于访问过的结点便可以弃之不用，只要先将其右孩子入栈保存，再将其左孩子入栈保存即可。先序遍历非递归算法举例

ABCDEGHF

A

AC

BBE

D

D^^E^G

G^^C^FFH^H^^遍历结果非递归算法实现——先序遍历void

Preorder(BinTreebt,VisitFuncvisit){ InitStack(S);

Push(S,bt);

while(!StackEmpty(S)){

Pop(S,p);

if(p){

visit(p);

Push(S,p->rchild);

Push(S,p->lchild);

} }}中序遍历的非递归算法实现思想实现中序遍历二叉树的非递归算法时，需要设一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。指针p从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问结点，然后移动到右子树上去。非递归算法实现——中序遍历voidInOrder(BinTreebt,VisitFuncvisit){

InitStack(S); p=bt;

while(p||!StackEmpty(S)){

if(p){

Push(S,p);

p=p->lchild;

}else{

Pop(S,p);

visit(p);

p=p->rchild; } }}非空进栈保存沿左子树向下移动为空向上移动，出栈，访问结点移动到右子树上先序遍历的非递归算法方法二实现思想修改前面介绍的中序遍历二叉树的非递归算法也可得到先序遍历二叉树的另一种非递归算法实现，即将访问结点的位置放在第一次指向该结点时。非递归算法——先序遍历实现二voidPreOrder(BinTreebt,VisitFuncvisit){

InitStack(S); p=bt;

while(p||!StackEmpty(S)){

if(p){

visit(p);

Push(S,p);

p=p->lchild;

}else{

Pop(S,p);

p=p->rchild; } }}非空进栈保存前，先访问沿左子树向下移动为空向上移动，出栈移动到右子树上后序遍历的非递归算法实现思想后序遍历时，分别从左子树和右子树共两次返回根结点，只有从右子树返回时才访