数据结构二叉树遍历

1、-. z.6.3 二叉树遍历二叉树遍历的定义所谓二叉树遍历，就是按*种规则访问二叉树的每个结点，且每个结点仅被访问一次。访问的含义十分广泛，包括对结点所作的各种操作与处理，如有关学生考试成绩的信息存储在一棵二叉树中，每个结点含有*、*、成绩等信息，在对这些信息进展管理时常常需要做这样的工作：1 打印每个学生的*、*、成绩等信息；2 将每个学生的成绩由百分制记分改为五级制记分；3 统计优、良、中、及格和不及格各档次的人数。在1中访问的含义是打印每个结点的信息；对于2，访问是对成绩进展修改的操作；3中访问是统计操作。不管访问的具体操作是什么，都必须做到既无重复，又无遗漏。一棵二叉树由根结点、左子树

2、、右子树三个根本单元组成，根结点处于一个分割左子树和右子树的位置，假设能遍历这三局部，则完成对一棵二叉树的遍历。假设以NNode、L(Left)、R(Right)分别代表访问根结点、遍历左子树、遍历右子树，则访问二叉树结点的规则可有NLR、LNR、LRN三种遍历和NRL、RNL、RLN三种逆遍历方式。一般限定先左后右，仅讨论前三种遍历，分别称之为前序遍历Preorder Traversal、中序遍历Inorder Traversal和后序遍历Postorder Traversal。基于二叉树的递归定义，可得三种遍历二叉树的递归定义： 前序遍历二叉树中序遍历二叉树后序遍历二叉树1 根 2 3 左

3、子树 右子树 2 根1 3 左子树 右子树 3 根1 2 左子树 右子树假设二叉树为空，则空操作；否则1访问根结点；2前序遍历左子树；3前序遍历右子树。假设二叉树为空，则空操作；否则1中序遍历左子树； 2访问根结点；3中序遍历右子树。假设二叉树为空，则空操作；否则1后序遍历左子树；2后序遍历右子树。3访问根结点；从上述定义可以看出，三种遍历的不同之处仅在于访问根结点、遍历左、右子树的先后次序不同。前序是指最先访问根结点；中序是指根结点在访问左、右子树之间被访问；后序是指根结点在左、右子树访问之后被访问。对于如图6.15所示的二叉树，前序遍历该二叉树时的结点访问序列为：A B D E G C F

4、 H I；中序访问序列为：D B G E A C H F I；后序访问序列为：D G E B H I F C A。 A B C D E F G H I图6.16 二叉树遍历前序遍历算法描述1递归算法由前序遍历二叉树的递归定义，容易得到相应的递归算法。前序遍历首先访问根结点，再访问左子树，然后访问右子树。对左子树的访问，也是先访问其根结点，再访问左其子树，然后访问其右子树，如此反复，逐步将大树的访问分解为左、右子树的访问，直到其子树为空。这是一个典型的递归模型。假设二叉树以二叉链表存储，对结点的访问操作简化为输出打印结点值，可根据实际应用具体化为其他操作，则前序遍历二叉树的递归算法如下：算法6.

5、1void Preorder(Bitree T)/*前序遍历二叉树的递归算法*/If (T)Printf(%d,T-data); /访问根结点Preorder(T-Lchild); / 遍历左子树Preorder(T-Rchild); / 遍历右子树return; 如图6.17所示为前序遍历二叉树的过程示意图。带箭头的包围虚线表示前序遍历过程中所走的一条搜索路径，其中向下的箭头表示向更深一层的递归调用，向上的箭头表示从递归调用返回，包围虚线旁方形内的字符表示搜索路径中访问的结点，访问序列为：A B D E C F。 A A AB C B B C D E F D D E FA B D E C F

6、a前序遍历二叉树A B D E C F b前序遍历过程示意图图6.16二叉树前序遍历过程示意图2.非递归算法下面，我们来讨论前序遍历算法的非递归实现。一个具有递归特点的问题，如果用非递归的程序实现，通常可以借助于栈来实现递归层次调用时的参数传递。前序遍历的顺序为：NLR，在访问根结点后对根的左子树遍历，当左子树遍历完后沿走过的路线返回到根结点，再通过根结点找到其右子树。因此，为了在左子树遍历完后能够找到其右子树，该根结点必须在左子树遍历前入栈保存。假设栈为一顺序栈，二叉树遍历的非递归算法涉及栈的入栈、出栈等多种操作，将充分展示栈的威力，是栈构造的一个极好的应用。算法6.2#define MA*

7、LEN 100void preorder(Bitree T)/*前序遍历二叉树的递归算法*/Bitree StackMA*LEN,p; int top=0; p=T; do While( p!=NULL)Printf(%d,p-data); /访问根结点top+; /根结点入栈stacktop=p;p=p-Lchild; /指向左子树 if (top0)p=stacktop; /根结点出栈top-;p=p-Rchild; /指向右子树; while p!=NULL| (top!=0); / 当根结点不为空或者栈不空时3.算法分析假定是n个结点的二叉树，由于每个结点仅被访问一次，每个结点要进一次

8、栈，出一次栈，因此算法中的根本操作进栈、出栈、访问等操作均被执行一次，算法的时间复杂度为O(n)。算法中的栈所需最大容量与二叉树的深度直接相关。从6.17(b)中可以看出，栈中元素序列实际上是由二叉树的根结点到*个结点所经分支上的结点所组成的，所以栈中元素的个数最多等于二叉树的深度。而有n个结点二叉树深度的最大值为n (单支树的情况)，因此，栈所需要的最大容量不超过n。中序遍历算法描述中序遍历与前序遍历算法思想非常类似，以下我们只简单给出中序遍历递归与非递归算法。1递归算法中序遍历的顺序为：LNR，中序遍历与前序遍历的区别仅在于访问根结点、遍历左子树、遍历右子树三个操作的次序不同而已，访问根结

9、点的操作在遍历左子树与遍历右子树之间。只要重新安排三个操作的次序就可以得到中序遍历递归算法算法6.3 void Inorder(Bitree T)/*中序遍历二叉树的递归算法*/If (T)Inorder(T-Lchild); /遍历左子树Printf(%d,T-data); /访问根结点Inorder(T-Rchild); /遍历右子树return; 如图6.18所示为二叉树中序遍历过程。从A开场，向其左子树递归调用，直到左子树为空，访问其根结点，第一个被访问的结点为D，再遍历D的右子树，为空返回到结点B，遍历其右子树，依次类推，得到中序遍历的序列为：D B E A C F。 A AB C

10、B C B D E F D D E FD B E A C Fa中序遍历二叉树D B E AC F b中序遍历过程示意图图6.18二叉树中序遍历过程示意图2非递归算法中序遍历的过程是遍历根结点的所有左子树的左结点并入栈，直到结点为空返回，结点出栈，被访问，然后转右子树结点。中序遍历的非递归算法在算法6.2的根底上稍作修改即得算法6.4。算法6.4#define MA*LEN 100void Inorder(Bitree T)/*中序遍历二叉树的非递归算法*/Bitree StackMA*LEN,p; int top=0; p=T; do While( p!=NULL) top+; /根结点入栈s

11、tacktop=p;p=p-Lchild; /指向左子树 if (top0)p=stacktop; /根结点出栈top-;Printf(%d,p-data); /访问根结点p=p-Rchild; /指向右子树; while p!=NULL| (top!=0); / 当根结点不为空或者栈不空时3.算法分析上述算法与前序遍历算法类似，只是访问根结点的语句在程序中的位置不同，并不影响算法的复杂性。因此，n个结点的二叉树，中序遍历算法的时间复杂度仍为O(n)，栈所需要的最大容量不超过二叉树的深度。后序遍历算法描述1递归算法后序遍历的顺序为：LRN，后序遍历与前序遍历的区别在于访问根结点的操作在遍历左子

12、树与遍历右子树之后。调整三个操作的次序就可以得到后序遍历递归算法。算法6.5 void Postorder(Bitree T)/*后序遍历二叉树的递归算法*/If (T)Postorder(T-Lchild); /遍历左子树Postorder(T-Rchild); /遍历右子树Printf(%d,T-data); /访问根结点return; 如图6.19所示为二叉树后序遍历过程。从A开场，向其左子树递归调用，直到结点D，左子树为空，再遍历D的右子树，也为空返回，访问结点D，再返回到结点B，遍历其右子树，依次类推，得到后序遍历的序列为：D E B F C A ，如图6.19b中包围虚线旁的三角内

13、字符为访问结点。 A AB C B C D E F D E F D E B F C Aa后序遍历二叉树D E B F C A b后序遍历过程示意图图6.18 二叉树后序遍历过程示意图2. 非递归算法后序遍历的非递归算法比前序遍历、中序遍历要复杂。在后序遍历时，如果存在左子树，则首先查看该结点的左子树，在按后序遍历左子树时，该结点进栈保存，以便返回时遍历其右子树。在按后序遍历其右子树时，该结点还得进栈保存，因为该结点需在右子树访问完后才被访问。这样，树中的每个结点都应两次进栈、两次出栈。第一次出栈是在遍历访问完所有的左子树结点，出栈的目的是为了访问其右子树；第二次出栈是在遍历访问完所有的右子树结

14、点，出栈的目的是为了访问该根结点。如何区分两次出栈？方法一是为每个结点设置标志位tagi: 0 访问左子树，需出栈找右子树 tagi=1 访问右子树，需出访问该结点算法6.6#define MA*LEN 100void Postorder1(Bitree T)/*后序遍历二叉树的非递归算法一*/Bitree StackMA*LEN,p; int tagMA*LEN,top=0，b; p=T; do While( p!=NULL) top+; /根结点入栈stacktop=p;tagtop=0; /设置标志位p=p-Lchild; /指向左子树 b=1; while (top!=0) &b p=

15、stacktop; /根结点出栈if (tagtop= =1)top-;Printf(%d,p-data); /访问根结点 else p=p-Rchild; /指向右子树tagtop=1;b=0; ; while p!=NULL| (top!=0); / 当根结点不为空或者栈不空时方法二是设一指针q，用于记住最近一次被访问的结点。这种方法不需要记住什么时候应访问根结点，不必为每个结点设立标志位，只需在结点每次出栈前判断其右子树是否为空，假设为空，即不存在右孩子，则该结点出栈应被访问；假设右子树非空但已遍历完毕，即它的右孩子恰好是最近一次访问的结点，则栈顶元素出栈应被访问；假设右子树非空而且尚未

16、遍历，即它的右孩子不是最近一次访问的结点，则现在不访问栈顶元素所指结点，而应去遍历右子树。因此，在遍历过程中，只需要用一指针记住最近访问过的结点即可。算法6.7#define MA*LEN 100void Postorder2(Bitree T)/*后序遍历二叉树的非递归算法二*/Bitree StackMA*LEN,p，q; int top=0，b; p=T; do While( p!=NULL) top+; /根结点入栈stacktop=p;p=p-Lchild; /指向左子树 b=1;q=NULL; while (top!=0) & b p=stacktop; /根结点出栈if p-rc

17、hild=q /栈顶元素所指结点其右子树是否为空或者其右子树是否为最近被访问的结点top-;Printf(%d,p-data); /访问根结点q=p; /q指向最近被访问的结点 else p=p-Rchild; /指向右子树b=0; ; while p!=NULL| (top!=0); / 当根结点不为空或者栈不空时3.算法分析上述算法与前序、中序遍历算法相比要复杂一些，理论上分析需要二次入栈，二次出栈，但从算法的实现来看，第一次并未真正出栈，只需取栈顶元素作判断即可，也就不需二次入栈。因此，对算法的复杂性并没有多大影响，n个结点的二叉树，后序遍历算法的时间复杂度仍为O(n)，栈所需要的最大容

18、量在小于二叉树的深度时不会出现溢出。遍历算法的应用遍历二叉树是二叉树各种操作运算的根底，很多操作可以在遍历过程中完成。如前所述，遍历算法中对每个结点进展一次访问操作，而访问结点的操作可以是多种形式及多个操作。利用这一特点，根据遍历算法的程序框架，适当修改访问操作的内容，便可得到求解许多问题的算法，如求二叉树的结点数、叶子数，判定结点的层次等。因此，二叉树遍历算法是二叉树应用算法的根底，其程序框架是非常根底又相当重要。下面给出几个典型问题的求解。例6.1求二叉树T中的叶子结点数本算法求二叉树T中的结点数，只需将遍历算法中的访问操作改为条件计数操作，即在访问结点时判断该结点是否为叶子，假设为叶子，

19、将该叶子结点的数目1累加到一个全局变量n中n初值为0,每个结点被访问时即被判断、条件计数。算法如下：算法6.8void Inord-Leaves( Bitree T) /*将二叉树T中的结点数累加到全局变量n中，n初值为0*/if (T)Inorder-Leaves(T-Lchild);If (T-Lchild = = NULL) & (T-Rchild = = NULLl) n=n+1;Inorder-Leaves(T-Lchild);算法6.8是一个标准中序遍历算法，其访问操作为是否为叶子的判断和累加计数。该算法也可很方便地改为前序遍历和后序遍历算法。例6.2 建立二叉树的存储构造二叉链表

20、建立二叉树的存储构造是对二叉树进展操作的前提，也就是说，对二叉树的操作必须是在建立二叉树存储构造的根底上进展，包括遍历操作。如图6.20(a)所示的二叉树，如何建立其图6.20(b)所示的二叉链表呢？假设按其前序遍历的线性顺序：A B # # C D # E # # # (空子树用表示)输入来建立二叉链表，T为指向根结点的指针，首先输入一个根结点，假设输入的是一个特殊字符如，则说明该二叉树为空树，即TNULL；否则，申请一个结点空间，输入的字符赋给T-data，之后依次递归建立其左子树T-Lchild和T-Rchild。按前序遍历算法框架设计该算法如下： A A B C B C D D E E

21、a二叉树例如 (b) 二叉链表图6.19 二叉树及其二叉链表算法6.9 void CreateBiTree ( BiTree & T) /*按前序遍历序列输入结点字符，建立二叉链表存储构造*/ scanf (&ch); if (ch=#) T= NULL; /建空树 else if (!(T= (BiTNode *)malloc(sizeof (BiTNode ) /生成根结点printf (OVERFLOW); return;T-data =ch;CreateBiTree (T -Lchild); /递归建立左子树CreateBiTree (T -Rchild); /递归建立右子树 retu

22、rn ;算法6.9是一个标准前序遍历算法，其访问操作为根结点生成操作。例6.3 求二叉树的高度二叉树的高度为二叉树中所有结点的最大层次数。结点的层次从根结点开场递推，设二叉树根结点的层次数为1，其子树根结点在第2层上，依此类推，第k层结点的子树根结点在第k+1层。因此求二叉树的高度，可在前序遍历二叉树的过程中求每个结点的层次数，其中的最大值即为二叉树的高度。算法6.10void BiTreeHeight ( BiTree T,int h,int &Height) /*求二叉树的高度Height，初值为0，h为T所指向的结点所在层次，初值为1*/if (T) if (hHeight) Heigh

23、t=h;BiTreeHeight ( T-Lchild, h+1,Height); BiTreeHeight ( T-Rchild, h+1,Height);算法6.10也是一个标准的前序遍历算法，其访问操作为当前访问结点的层次数h与当前求得的最大层次数Height比拟，Height取大值。该算法参数表中设置的值参h，始终保持和当前T所指结点层次一致，这是很多遍历应用算法中采用的一种技巧，请注意掌握这种技巧的应用。图6.19(a)所示的二叉树，求其高度算法执行过程如图6.20所示，向下的虚线表示递归调用，虚线旁边括号内的值为调用传递的参数值，向上的虚线表示调用返回，虚线旁的值为调用返回值。He

24、ight简化表示为H，注意H与h值得区别。图6.20 前序遍历求二叉树高度算法执行过程求二叉树高度也可通过后序遍历二叉树来得到。二叉树高度可递归定义为：假设二叉树为空，则其高度为0;否则其高度等于左或右子树的最大高度加1。由此递归定义得到递归模型为： 0 T=NULLHeight(T)= Ma* (Height(T-Lchild) , Height(T-Rchild)+1 TNULL从而得到以下算法：算法6.11void BiTreeHeight ( BiTree T) /*求二叉树的高度Height*/if (！T) return 0 else HL=BiTreeHeight ( T-Lch

25、ild); HR=BiTreeHeight ( T-Rchild);if (HL=HR) return HL+1;else return HR+1;例6.3 表达式求值表达式的计算曾在第三章作为栈的典型应用进展了讨论，这里，选择二叉树这种数据构造存储表达式，讨论其求值问题。一般情况下，一个表达式由一个运算符和两个操作数构成，两个操作数之间有次序之分，并且操作数也可是表达式，这种构造类似于二叉树，因此，可以用二叉树表示表达式。表示表达式的二叉树称为表达式树E*pression Trees,这类二叉树具有以下特点：1. 每个叶子是操作数；2. 根结点和内部结点是操作符；3. 子树是子表达式树。如表达式a*(b+c)+d,可表示成图6.22所示的二叉树。前序遍历这棵二叉树，得到线性序列：+*a+bcd，这是表达式的前缀形式，或称为波兰表示。中序遍历这棵二叉树，得到线性序列：a*b+c+d，这恰是表达式的中缀形式。后序遍历这棵二叉树，得到