数据结构.docx

《数据结构.docx》由会员分享，可在线阅读，更多相关《数据结构.docx（18页珍藏版）》请在三一办公上搜索。

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

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

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

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

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

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

7、N 100 void preorder(Bitree T) /*前序遍历二叉树的递归算法*/ Bitree StackMAXLEN,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 | (top!=0); / 当根结点不为空或者栈不空时 3.算法分析 假定是n个结点的二叉树，由于每个结点仅被访问一次，每个

8、结点要进一次栈，出一次栈，因此算法中的基本操作均被执行一次，算法的时间复杂度为O(n)。 算法中的栈所需最大容量与二叉树的深度直接相关。从6.17(b)中可以看出，栈中元素序列实际上是由二叉树的根结点到某个结点所经分支上的结点所组成的，所以栈中元素的个数最多等于二叉树的深度。而有n个结点二叉树深度的最大值为n (单支树的情况)，因此，栈所需要的最大容量不超过n。 6.3.3 中序遍历算法描述 中序遍历与前序遍历算法思想非常类似，以下我们只简单给出中序遍历递归与非递归算法。 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

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

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

12、序遍历的顺序为：LRN，后序遍历与前序遍历的区别在于访问根结点的操作在遍历左子树与遍历右子树之后。调整三个操作的次序就可以得到后序遍历递归算法。 算法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，遍历其右子

13、树，依次类推，得到后序遍历的序列为：D E B F C A ，如图6.19中包围虚线旁的三角内字符为访问结点。 A A B C B C D E F D E F D E B F C A 后序遍历二叉树D E B F C A 后序遍历过程示意图 图6.18 二叉树后序遍历过程示意图 2. 非递归算法 后序遍历的非递归算法比前序遍历、中序遍历要复杂。在后序遍历时，如果存在左子树，则首先查看该结点的左子树，在按后序遍历左子树时，该结点进栈保存，以便返回时遍历其右子树。在按后序遍历其右子树时，该结点还得进栈保存，因为该结点需在右子树访问完后才被访问。这样，树中的每个结点都应两次进栈、两次出栈。第一次出栈

14、是在遍历访问完所有的左子树结点，出栈的目的是为了访问其右子树；第二次出栈是在遍历访问完所有的右子树结点，出栈的目的是为了访问该根结点。 如何区分两次出栈？方法一是为每个结点设置标志位tagi: 0 访问左子树，需出栈找右子树 tagi= 1 访问右子树，需出访问该结点 算法6.6 #define MAXLEN 100 void Postorder1(Bitree T) /*后序遍历二叉树的非递归算法一*/ Bitree StackMAXLEN,p; int tagMAXLEN,top=0，b; p=T; do While( p!=NULL) top+; /根结点入栈 stacktop=p; t

15、agtop=0; /设置标志位 p=p-Lchild; /指向左子树 b=1; while (top!=0) &b p=stacktop; /根结点出栈 if (tagtop= =1) top-; Printf(“%d”,p-data); /访问根结点 else p=p-Rchild; /指向右子树 tagtop=1; b=0; ; while | (top!=0); / 当根结点不为空或者栈不空时 方法二是设一指针q，用于记住最近一次被访问的结点。这种方法不需要记住什么时候应访问根结点，不必为每个结点设立标志位，只需在结点每次出栈前判断其右子树是否为空，若为空，即不存在右孩子，则该结点出栈应

16、被访问；若右子树非空但已遍历完毕，即它的右孩子恰好是最近一次访问的结点，则栈顶元素出栈应被访问；若右子树非空而且尚未遍历，即它的右孩子不是最近一次访问的结点，则现在不访问栈顶元素所指结点，而应去遍历右子树。因此，在遍历过程中，只需要用一指针记住最近访问过的结点即可。 算法6.7 #define MAXLEN 100 void Postorder2(Bitree T) /*后序遍历二叉树的非递归算法二*/ Bitree StackMAXLEN,p，q; int top=0，b; p=T; do While( p!=NULL) top+; /根结点入栈 stacktop=p; p=p-Lchild

17、; /指向左子树 b=1;q=NULL; while (top!=0) & b p=stacktop; /根结点出栈 if p-rchild=q /栈顶元素所指结点其右子树是否为空 或者其右子树是否为最近被访问的结点 top-; Printf(“%d”,p-data); /访问根结点 q=p; /q指向最近被访问的结点 else p=p-Rchild; /指向右子树 b=0; ; while | (top!=0); / 当根结点不为空或者栈不空时 3.算法分析 上述算法与前序、中序遍历算法相比要复杂一些，理论上分析需要二次入栈，二次出栈，但从算法的实现来看，第一次并未真正出栈，只需取栈顶元素作

18、判断即可，也就不需二次入栈。因此，对算法的复杂性并没有多大影响，n个结点的二叉树，后序遍历算法的时间复杂度仍为O(n)，栈所需要的最大容量在小于二叉树的深度时不会出现溢出。 6.3.5遍历算法的应用 遍历二叉树是二叉树各种操作运算的基础，很多操作可以在遍历过程中完成。如前所述，遍历算法中对每个结点进行一次访问操作，而访问结点的操作可以是多种形式及多个操作。利用这一特点，根据遍历算法的程序框架，适当修改访问操作的内容，便可得到求解许多问题的算法，如求二叉树的结点数、叶子数，判定结点的层次等。因此，二叉树遍历算法是二叉树应用算法的基础，其程序框架是非常基础又相当重要。下面给出几个典型问题的求解。

19、例6.1 求二叉树T中的叶子结点数 本算法求二叉树T中的结点数，只需将遍历算法中的访问操作改为条件计数操作，即在访问结点时判断该结点是否为叶子，若为叶子，将该叶子结点的数目1累加到一个全局变量n中,每个结点被访问时即被判断、条件计数。算法如下： 算法6.8 void 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);

20、算法6.8是一个“标准”中序遍历算法，其访问操作为是否为叶子的判断和累加计数。该算法也可很方便地改为前序遍历和后序遍历算法。 例6.2 建立二叉树的存储结构二叉链表 建立二叉树的存储结构是对二叉树进行操作的前提，也就是说，对二叉树的操作必须是在建立二叉树存储结构的基础上进行，包括遍历操作。如图6.20(a)所示的二叉树，如何建立其图6.20(b)所示的二叉链表呢？假设按其前序遍历的线性顺序：A B # # C D # E # # # (空子树用“”表示)输入来建立二叉链表，T为指向根结点的指针，首先输入一个根结点，若输入的是一个特殊字符如“”，则表明该二叉树为空树，即TNULL；否则，申请一个

21、结点空间，输入的字符赋给T-data，之后依次递归建立其左子树T-Lchild和T-Rchild。按前序遍历算法框架设计该算法如下： A A B C B C D D E E 二叉树示例 (b) 二叉链表 图6.19 二叉树及其二叉链表 算法6.9 void CreateBiTree ( BiTree & T) /* 按前序遍历序列输入结点字符，建立二叉链表存储结构*/ scanf (&ch); if (ch=#”) T= NULL; /建空树 else if (!(T= (BiTNode *)malloc(sizeof (BiTNode ) /生成根结点 printf (“OVERFLOW”)

22、; return; T-data =ch; CreateBiTree (T -Lchild); /递归建立左子树 CreateBiTree (T -Rchild); /递归建立右子树 return ; 算法6.9是一个“标准”前序遍历算法，其访问操作为根结点生成操作。 例6.3 求二叉树的高度 二叉树的高度为二叉树中所有结点的最大层次数。结点的层次从根结点开始递推，设二叉树根结点的层次数为1，其子树根结点在第2层上，依此类推，第k层结点的子树根结点在第k+1 层。因此求二叉树的高度，可在前序遍历二叉树的过程中求每个结点的层次数，其中的最大值即为二叉树的高度。 算法6.10 void BiTre

23、eHeight ( BiTree T,int h,int &Height) /*求二叉树的高度Height，初值为0，h为T所指向的结点所在层次，初值为1*/ if (T) if (hHeight) Height=h; BiTreeHeight ( T-Lchild, h+1,Height); BiTreeHeight ( T-Rchild, h+1,Height); 算法6.10也是一个“标准”的前序遍历算法，其访问操作为当前访问结点的层次数h与当前求得的最大层次数Height比较，Height取“大值”。该算法参数表中设置的值参h，始终保持和当前T所指结点层次一致，这是很多遍历应用算法中采

24、用的一种技巧，请注意掌握这种技巧的应用。图6.19(a)所示的二叉树，求其高度算法执行过程如图6.20所示，向下的虚线表示递归调用，虚线旁边括号内的值为调用传递的参数值，向上的虚线表示调用返回，虚线旁的值为调用返回值。Height简化表示为H，注意H与h值得区别。 图6.20 前序遍历求二叉树高度算法执行过程 求二叉树高度也可通过后序遍历二叉树来得到。二叉树高度可递归定义为：若二叉树为空，则其高度为0;否则其高度等于左子树的最大高度加1。由此递归定义得到递归模型为： 0 T=NULL Height(T)= Max (Height(T-Lchild) , Height(T-Rchild)+1 T

25、NULL 从而得到以下算法： 算法6.11 void BiTreeHeight ( BiTree T) /*求二叉树的高度Height*/ if (！T) return 0 else HL=BiTreeHeight ( T-Lchild); HR=BiTreeHeight ( T-Rchild); if (HL=HR) return HL+1; else return HR+1; 例6.3 表达式求值 表达式的计算曾在第三章作为栈的典型应用进行了讨论，这里，选择二叉树这种数据结构存储表达式，讨论其求值问题。一般情况下，一个表达式由一个运算符和两个操作数构成，两个操作数之间有次序之分，并且操作数

26、也可是表达式，这种结构类似于二叉树，因此，可以用二叉树表示表达式。表示表达式的二叉树称为表达式树,这类二叉树具有以下特点： 1. 每个叶子是操作数； 2. 根结点和内部结点是操作符； 3. 子树是子表达式树。 如表达式a*(b+c)+d,可表示成图6.22所示的二叉树。前序遍历这棵二叉树，得到线性序列：+*a+bcd，这是表达式的前缀形式，或称为波兰表示。中序遍历这棵二叉树，得到线性序列：a*b+c+d，这恰是表达式的中缀形式。后序遍历这棵二叉树，得到线性序列：abc+*d+，这是表达式的后缀形式，或称为逆波兰表示。 + * d a + b c 图6.22 表达式a*(b+c)+d的二叉树表示

27、 下面主要研究算术表达式求值问题，而逻辑表达式的计算可类似实现。为简单起见，问题简化为：表达式中只有二元运算，运算符为、*、/，操作数以单字符的简单变量表示。表达式求值需按运算符的优先关系，从左至右计算。表达式a*(b+c)+d 按优先关系分解成： 第一操作数：a*(b+c) 运算符：+ 第二操作数：d 在进行该运算时，必须先计算出第一操作数的值，类似将第一操作数分解为：a、*、b+c，依此类推。因此，在处理一“运算符”前，必须先求出其左、右操作数表达式的值，由此可见，表达式求值的过程实际上是后序遍历二叉树的过程，先计算子树，直到整个表达式变成单值为止。 对表达式树采用二叉链表存储时，每个结点

28、增加一个结果域，结点的形式为 Lchild data result Rchild 基于此，给出算术表达式求值的算法如下： 算法6.12 void value ( BiTree T) /*算术表达式求值*/ if (！T) T-result= 0;return; else value ( T-Lchild); /求左子树的值 value ( T-Rchild); /求右子树的值 switch (T-data) case + ：T-result= (T-Lchild-result)+( T-Rchild-result);break; case - ：T-result= (T-Lchild-result)-( T-Rchild-result);break; case * ：T-result= (T-Lchild-result)*( T-Rchild-result);break; case / ：T-result= (T-Lchild-result)/( T-Rchild-result);break; default : T-result=T-data;break; return;