数据结构(二叉树遍历).docVIP

. . 6.3 二叉树遍历 6.3.1 二叉树遍历的定义 所谓二叉树遍历，就是按某种规则访问二叉树的每个结点，且每个结点仅被访问一次。“访问”的含义十分广泛，包括对结点所作的各种操作与处理，如有关学生考试成绩的信息存储在一棵二叉树中，每个结点含有学号、姓名、成绩等信息，在对这些信息进行管理时常常需要做这样的工作： （1）?????? 打印每个学生的学号、姓名、成绩等信息； （2）?????? 将每个学生的成绩由百分制记分改为五级制记分； （3）?????? 统计优、良、中、及格和不及格各档次的人数。 在（1）中“访问”的含义是打印每个结点的信息；对于（2），“访问”是对成绩进行修改的操作；（3）中“访问”是统计操作。不管访问的具体操作是什么，都必须做到既无重复，又无遗漏。 一棵二叉树由根结点、左子树、右子树三个基本单元组成，根结点处于一个分割左子树和右子树的位置，若能遍历这三部分，则完成对一棵二叉树的遍历。假如以N（Node）、L(Left)、R(Right)分别代表访问根结点、遍历左子树、遍历右子树，则访问二叉树结点的规则可有NLR、LNR、LRN三种遍历和NRL、RNL、RLN三种逆遍历方式。一般限定先左后右，仅讨论前三种遍历，分别称之为前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。基于二叉树的递归定义，可得三种遍历二叉树的递归定义： 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 1 根 2??????????????????????????? 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 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． 递归算法 由前序遍历二叉树的递归定义，容易得到相应的递归算法。前序遍历首先访问根结点，再访问左子树，然后访问右子树。对左子树的访问，也是先访问其根结点，再访问左其子树，然后访问其右子树，如此反复，逐步将“大树”的访问分解为“左、右子树”的访问，直到其子树为空。这是一个典型的递归模型。假设二叉树以二叉链表存储，对结点的访问操作简化为输出打印结点值，可根据实际应用具体化为其他操作，则前序遍历二叉树的递归算法如下： ? 算法6.1 void 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 A ? B C