Python中的关键算法之“二叉树的遍历算法”

大家好，欢迎来到IT知识分享网。

本实战技能是对二叉遍历（即二叉树的遍历算法）的实现。运行程序得到的结果如下图所示。

二叉查找结果展示

【技术要点】

要实现本案例，需要掌握二叉树遍历算法的知识。

从二叉树的递归定义可知，一棵非空的二叉树由根节点及左、右子树组成。因此，在任意给定节点上，可以按某种次序执行以下3种操作。

（1）访问根节点（N）。

（2）遍历该节点的左子树（L）。

（3）遍历该节点的右子树（R）。

以上3种操作有6种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。

前三种次序与后三种次序对称，故只讨论NLR、LNR、LRN。这3种次序分别被命名为前序遍历、中序遍历和后序遍历。二叉树如图2-26所示，各种遍历方式如下。

示例二叉树

（1）前序遍历（NLR）：访问根节点的操作发生在遍历其左、右子树之前（DBACEGF）。

（2）中序遍历（LNR）：访问根节点的操作发生在遍历其左、右子树的中间（ABCDEFG）。

（3）后序遍历（LRN）：访问根节点的操作发生在遍历其左、右子树之后（ACBFGED）。

【主体设计】

二叉树遍历的实现流程如下图所示。

二叉树遍历流程图

二叉树遍历的编程步骤如下。

Step1：构建类的函数，将根节点、左子树、右子树进行基本的初始化，即构建一个空的二叉树。

Step2：判断二叉树是否为空，若为空则没有值返回。若为前序遍历，则先访问根节点，再访问左子树，最后访问右子树，递归实现。

Step3：判断二叉树是否为空，若为空则没有值返回。若为中序遍历，则先访问左子树，再访问根节点，最后访问右子树，递归实现。

Step4：判断二叉树是否为空，若为空则没有值返回。若为后序遍历，则先访问左子树，再访问右子树，最后访问根节点，递归实现。

Step5：给出一个二叉树，通过调用前面已经定义好的各个遍历方式的函数，对该二叉树进行遍历处理，使用print( )函数输出遍历结果。

【编程实现】

本实战技能使用PyCharm工具进行编写，建立相关的源文件【二叉遍历.py】，在界面输入代码。参考下面的详细步骤，编写具体代码，具体步骤及代码如下所示。

Step1：构建一个空的二叉树，初始化根节点、左子树、右子树，代码如下所示。

1. class Node:

2. def _init_(self, value=None, left=None, right=None):

3. self.value = value

4. self.left = left # 左子树

5. self.right = right # 右子树

Step2：定义一个用于对二叉树进行前序遍历的函数，代码如下所示。

1. def preTraverse(root):

2. # 前序遍历

3. if root == None:

4. return

5. print(root.value, end=” “)

6. preTraverse(root.left)

7. preTraverse(root.right)

Step3：定义一个用于对二叉树进行中序遍历的函数，代码如下所示。

1. def midTraverse(root):

2. # 中序遍历

3. if root == None:

4. return

5. midTraverse(root.left)

6. print(root.value, end=” “)

7. midTraverse(root.right)

Step4：定义一个用于对二叉树进行后序遍历的函数，代码如下所示。

1. def afterTraverse(root):

2. # 后序遍历

3. if root == None:

4. return

5. afterTraverse(root.left)

6. afterTraverse(root.right)

7. print(root.value, end=” “)

Step5：将二叉树各个节点的数据录入空的二叉树中，再对二叉树的数据进行遍历输出，代码

如下所示。

1. if _name_ == ‘_main_’:

2. print(” 二叉遍历案例 “)

3. root=Node(‘D’, Node(‘B’, Node(‘A’), Node(‘C’)), Node(‘E’, right=Node(‘G’,

4. Node(‘F’))))

5. print(‘ 前序遍历：’)

6. preTraverse(root)

7. print(‘\n 中序遍历：’)

8. midTraverse(root)

9. print(‘\n 后序遍历：’)

10. afterTraverse(root)