《数据结构二叉树遍历资料资料》由会员分享，可在线阅读，更多相关《数据结构二叉树遍历资料资料（14页珍藏版）》请在金锄头文库上搜索。
1、6.3 二叉树遍历6.3.1 二叉树遍历的定义所谓二叉树遍历，就是按某种规则访问二叉树的每个结点，且每个结点仅被访问一次。“访问”的含义十分广泛，包括对结点所作的各种操作与处理，如有关学生考试成绩的信息存储在一棵二叉树中，每个结点含有学号、姓名、成绩等信息，在对这些信息进行管理时常常需要做这样的工作：（1） 打印每个学生的学号、姓名、成绩等信息；（2） 将每个学生的成绩由百分制记分改为五级制记分；（3） 统计优、良、中、及格和不及格各档次的人数。在（1）中“访问”的含义是打印每个结点的信息；对于（2），“访问”是对成绩进行修改的操作；（3）中“访问”是统计操作。不管访问的具体操作是什么，都必须
2、做到既无重复，又无遗漏。一棵二叉树由根结点、左子树、右子树三个基本单元组成，根结点处于一个分割左子树和右子树的位置，若能遍历这三部分，则完成对一棵二叉树的遍历。假如以N（Node）、L(Left)、R(Right)分别代表访问根结点、遍历左子树、遍历右子树，则访问二叉树结点的规则可有NLR、LNR、LRN三种遍历和NRL、RNL、RLN三种逆遍历方式。一般限定先左后右，仅讨论前三种遍历，分别称之为前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。基于二叉树的递归定义，可得三种遍历二叉树的递归定义
3、： 前序遍历二叉树中序遍历二叉树后序遍历二叉树1 根 2 3 左子树 右子树 2 根1 3 左子树 右子树 3 根1 2 左子树 右子树若二叉树为空，则空操作；否则（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。若二叉树为空，则空操作；否则（1）中序遍历左子树； （2）访问根结点；（3）中序遍历右子树。若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；从上述定义可以看出，三种遍历的不同之处仅在于访问根结点、遍历左、右子树的先后次序不同。“前序”是指最先访问根结点；“中序”是指根结点在访问左、右子树之间被访问；“后序”是指根结点在左、右子树访
4、问之后被访问。对于如图6.15所示的二叉树，前序遍历该二叉树时的结点访问序列为：A B D E G C F 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 二叉树遍历6.3.2 前序遍历算法描述1 递归算法由前序遍历二叉树的递归定义，容易得到相应的递归算法。前序遍历首先访问根结点，再访问左子树，然后访问右子树。对左子树的访问，也是先访问其根结点，再访问左其子树，然后访问其右子树，如此反复，逐步将“大树”的访问分解为“左、右子树”的访问，直到其子树为空。这是一个典型的递归模型。假设二
5、叉树以二叉链表存储，对结点的访问操作简化为输出打印结点值，可根据实际应用具体化为其他操作，则前序遍历二叉树的递归算法如下：算法6.1void Preorder(Bitree T)/*前序遍历二叉树的递归算法*/If (T)Printf(“%d”,T-data); /访问根结点Preorder(T-Lchild); / 遍历左子树Preorder(T-Rchild); / 遍历右子树return; 如图6.17所示为前序遍历二叉树的过程示意图。带箭头的包围虚线表示前序遍历过程中所走的一条搜索路径，其中向下的箭头表示向更深一层的递归调用，向上的箭头表示从递归调用返回，包围虚线旁方形内的字符表示搜索
6、路径中访问的结点，访问序列为：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（a）前序遍历二叉树A B D E C F （b）前序遍历过程示意图 图6.16二叉树前序遍历过程示意图2.非递归算法下面，我们来讨论前序遍历算法的非递归实现。一个具有递归特点的问题，如果用非递归的程序实现，通常可以借助于栈来实现递归层次调用时的参数传递。前序遍历的顺序为：NLR，在访问根结点后对根的左子树遍历，当左子树遍历完后沿走过的路线返回到根结点，再通过根结点找到其右子树。因此，为了在左子树遍历完后能够找到其右子树，该根结点必须在左子树遍历前入栈保存。假设
7、栈为一顺序栈，二叉树遍历的非递归算法涉及栈的入栈、出栈等多种操作，将充分展示栈的威力，是栈结构的一个极好的应用。算法6.2#define MAXLEN 100void 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; /指向右子树; whi
8、le （p!=NULL）| (top!=0); / 当根结点不为空或者栈不空时3.算法分析假定是n个结点的二叉树，由于每个结点仅被访问一次，每个结点要进一次栈，出一次栈，因此算法中的基本操作（进栈、出栈、访问等操作）均被执行一次，算法的时间复杂度为O(n)。算法中的栈所需最大容量与二叉树的深度直接相关。从6.17(b)中可以看出，栈中元素序列实际上是由二叉树的根结点到某个结点所经分支上的结点所组成的，所以栈中元素的个数最多等于二叉树的深度。而有n个结点二叉树深度的最大值为n (单支树的情况)，因此，栈所需要的最大容量不超过n。6.3.3 中序遍历算法描述中序遍历与前序遍历算法思想非常类似，以下
9、我们只简单给出中序遍历递归与非递归算法。1 递归算法中序遍历的顺序为：LNR，中序遍历与前序遍历的区别仅在于访问根结点、遍历左子树、遍历右子树三个操作的次序不同而已，访问根结点的操作在遍历左子树与遍历右子树之间。只要重新安排三个操作的次序就可以得到中序遍历递归算法算法6.3 void Inorder(Bitree T)/*中序遍历二叉树的递归算法*/If (T)Inorder(T-Lchild); /遍历左子树Printf(“%d”,T-data); /访问根结点Inorder(T-Rchild); /遍历右子树return; 如图6.18所示为二叉树中序遍历过程。从A开始，向其左子树递归调用
10、，直到左子树为空，访问其根结点，第一个被访问的结点为D，再遍历D的右子树，为空返回到结点B，遍历其右子树，依次类推，得到中序遍历的序列为：D B E A C F。 A AB C B C B D E F D D E FD B E A C F（a）中序遍历二叉树D B E AC F （b）中序遍历过程示意图 图6.18二叉树中序遍历过程示意图2 非递归算法中序遍历的过程是遍历根结点的所有左子树的左结点并入栈，直到结点为空返回，结点出栈，被访问，然后转右子树结点。中序遍历的非递归算法在算法6.2的基础上稍作修改即得算法6.4。算法6.4#define MAXLEN 100void Inorder(B
11、itree T)/*中序遍历二叉树的非递归算法*/Bitree StackMAXLEN,p; int top=0; p=T; do While( p!=NULL) top+; /根结点入栈stacktop=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)，栈所需要的最大容量不超过二叉树的深度。6.3.4 后序遍历算法描述1递归算法后序遍历的顺序为：LRN，后序遍历与前序遍历的区别在于访问根结点的操作在遍历左子树与遍历右子树之后。调整三个操作的
