数据结构(二叉树遍历)

《数据结构(二叉树遍历)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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三种逆遍历方式。一般限定先左后右，仅讨论前三种遍历，分别称之为前序遍历（PreorderTraversal）、中序遍历（InorderTraversal）和后序遍历（PostorderTr

3、aversal）。基于二叉树的递归定义，可得三种遍历二叉树的递归定义：前序遍历二叉树中序遍历二叉树后序遍历二叉树1根2                           3左子树右子树2根 1                        3左子树右子树3根 1                           2左子树右子树 若二叉树为空，则空操作；否则（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。 若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。 若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后

4、序遍历右子树。（3）访问根结点； 从上述定义可以看出，三种遍历的不同之处仅在于访问根结点、遍历左、右子树的先后次序不同。“前序”是指最先访问根结点；“中序”是指根结点在访问左、右子树之间被访问；“后序”是指根结点在左、右子树访问之后被访问。对于如图6.15所示的二叉树，前序遍历该二叉树时的结点访问序列为：ABDEGCFHI；中序访问序列为：DBGEACHFI；后序访问序列为：DGEBHIFCA。A BC DEF GHI图6.16二叉树遍历 6.3.2前序遍历算法描述1．递归算法由前序遍历二叉树的递归定义，容易得到相应的递归算法。前序遍历首先访问根结点，再访问左子树，然后

5、访问右子树。对左子树的访问，也是先访问其根结点，再访问左其子树，然后访问其右子树，如此反复，逐步将“大树”的访问分解为“左、右子树”的访问，直到其子树为空。这是一个典型的递归模型。假设二叉树以二叉链表存储，对结点的访问操作简化为输出打印结点值，可根据实际应用具体化为其他操作，则前序遍历二叉树的递归算法如下： 算法6.1voidPreorder(BitreeT)/*前序遍历二叉树的递归算法*/{If(T){Printf(“%d”,T->data);//访问根结点Preorder(T->Lchild);//遍历左子树Preorder(T->Rchild);//遍历右子树}r

6、eturn;}如图6.17所示为前序遍历二叉树的过程示意图。带箭头的包围虚线表示前序遍历过程中所走的一条搜索路径，其中向下的箭头表示向更深一层的递归调用，向上的箭头表示从递归调用返回，包围虚线旁方形内的字符表示搜索路径中访问的结点，访问序列为：ABDECF。  AAA BCBBC DEFDDEF ABDECF （a）前序遍历二叉树—ABDECF（b）前序遍历过程示意图图6.16二叉树前序遍历过程示意图 2.非递归算法下面，我们来讨论前序遍历算法的非递归实现。一个具有递归特点的问题，如果用非递归的程序实现，通常可以借助于栈来实现递归层次调用时的参数传递。前序遍历的顺序为：

7、NLR，在访问根结点后对根的左子树遍历，当左子树遍历完后沿走过的路线返回到根结点，再通过根结点找到其右子树。因此，为了在左子树遍历完后能够找到其右子树，该根结点必须在左子树遍历前入栈保存。假设栈为一顺序栈，二叉树遍历的非递归算法涉及栈的入栈、出栈等多种操作，将充分展示栈的威力，是栈结构的一个极好的应用。算法6.2#defineMAXLEN100voidpreorder(BitreeT)/*前序遍历二叉树的递归算法*/{BitreeStack[MAXLEN],p;inttop=0;p=T;do{While(p!=NULL){Printf(“