二叉树的遍历方法和递归实现

《二叉树的遍历方法和递归实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节二叉树的遍历方法和递归实现什么是二叉树的遍历？二叉树的遍历：是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。为什么要遍历二叉树？遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定的顺序对二叉树中的每个结点逐个进行访问。如何遍历二叉树？由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。遍历二叉树主要有4种方式：Ø先序遍历Ø中序遍历Ø后序遍历Ø层次遍历约定：用D表示访问根结点，用L表示遍历左子树，用R表示遍历右子树。先序遍历：用DLR表示，即先

2、访问根结点à再遍历根结点的左子树à最后遍历根结点的右子树。中序遍历：用LDR表示，即先遍历根结点的左子树à再访问根结点à最后遍历根结点的右子树。后序遍历：用LRD表示，即先遍历根结点的左子树à再遍历根结点的右子树à最后访问根结点。层次遍历：从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。注意：如何区分先序遍历、中序遍历和后序遍历？关键看一点：根结点什么时候被访问。如果最先访问根结点，就是先序遍历；如果在中间访问根结点，就是中序遍历；如果最后访问根结点，就是后序遍历。以图1所示的二叉树为例，下面将通过上述4种遍历方式分别来遍历这棵

3、二叉树。1.先序遍历(DLR)先序遍历的递归过程为：若二叉树为空，遍历结束；否则：(1)先访问根结点；(2)再遍历根结点的左子树；(3)最后遍历根结点的右子树。对图1所示的二叉树，首先访问根结点A，然后移动到A结点的左子树。A结点的左子树的根结点是B，于是访问B结点。移动到B的左子树，B结点的左子树的根结点是D，于是访问D结点。由于D结点没有左子树，因此移动D结点的右子树。D结点的右子树的根结点是G，于是访问G结点。现在就完成了对根结点和左子树的遍历，以类似的方法遍历根结点的右子树。先序遍历的示意图，如图2所示：图2先序遍历示意图按先序遍历得到的结点序列为：ABDGCEF2.

4、中序遍历中序遍历的递归过程为：若二叉树为空，遍历结束；否则：(1)先遍历根结点的左子树；(2)再访问根结点；(3)最后遍历根结点的右子树。对图1所示的二叉树，在访问根结点A之前，必须先遍历A结点的左子树，因此移动到B结点。在访问B结点之前，必须先遍历B结点的左子树，因此移动到D结点。在访问D结点之前，必须先遍历D结点的左子树，由于D结点的左子树是空的，于是就访问D结点。在访问D结点之后，必须遍历D结点的右子树，因此移动到G结点。在访问G结点之前，必须先遍历G结点的左子树，由于G结点没有左子树，于是就访问G结点。在访问G结点之后，必须遍历G结点的右子树，由于G结点的右子树是空的

5、，于是访问B结点。在访问B结点之后，必须遍历B结点的右子树，由于B结点的右子树是空的，于是访问A结点。在访问A结点之后，必须遍历A结点的右子树，因此移动到C结点。在访问C结点之前，必须先遍历C结点的左子树E，然后访问C，再访问F。中序遍历的示意图，如图3所示：图3中序遍历示意图按中序遍历得到的结点序列为：DGBAECF3.后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束；否则：(1)先遍历根结点的左子树；(2)再遍历根结点的右子树；(3)最后访问根结点。对于图1所示的二叉树，首先遍历根结点A的左子树。A结点的左子树的根结点是B，因此需要进一步移动到它的左子树。B结点的左子

6、树的根结点是D。D结点没有左子树，但有右子树，因此移动到它的右子树。D的右子树的根结点是G，G结点没有左子树和右子树，因此结点G是首先访问的结点。在访问了G结点之后，遍历D结点的右子树的流程就完成了，因此需要访问D结点。现在B结点的左子树的遍历就完成了。现在可以遍历B结点的右子树，因为B结点没有右子树，于是就访问B结点，这样A结点的左子树的遍历就完成了。以类似的方式遍历A结点的右子树。后序遍历的示意图，如图4所示：图4后序遍历示意图按后序遍历得到的结点序列为：GDBEFCA4.层次遍历层次遍历的过程：若二叉树为空，遍历结束；否则：从二叉树的第一层(根结点)开始，从上至下逐层遍

7、历，在同一层中，则按从左到右的顺序对结点逐个访问。对于图1所示的二叉树，其层次遍历的示意图，如图5所示：图5层次遍历示意图按层次遍历得到的结点序列为：ABCDEFG在C#中，二叉树的4种遍历方式的算法实现，如下所示：//二叉链表的类，实现二叉树的基本操作。publicclassLinkBiTree{privateNodehead;//头引用，指向二叉树中第一个结点。//头引用属性publicNodeHead{get{returnhead;}set{head=value;}}//构造函数