python实现二叉树并且遍历

2.1 二叉树的遍历

2.1.1 前序遍历 (根左右)

二叉树的前序遍历的步骤如下：

访问树的根节点----> 访问当前节点的左子树---->若当前节点无左子树，访问当前节点的右子树。

以上图为例，对其进行前序遍历的步骤为：

1. 先访问根节点，得到1

2. 访问根节点1的左子节点2，发现左子节点2还有左子节点4，继续向下访问，直到最后一个左子节点8，发现8为叶子节点。继续访问其父节点4的右子节点9，发现右子节点9为叶子节点。得到序列2、4、8、9.

3. 根据“根左右”的顺序，访问左子节点2的右子节点5，其有左子节点10，但是10为叶子节点，得到序列：5、10。至此二叉树的左子树遍历完毕，得到以下序列：1、2、4、8、9、5、10。

4. 以类似的方式访问根节点1的右子节点3，访问左子节点6，其为叶子节点，继续访问其兄弟节点的右子节点7。至此，二叉树的右子树遍历完毕，得到以下序列：3、6、7。至此整棵二叉树的遍历完毕。

得到的结果为：1、2、4、8、9、5、10、3、6、7。

实现前序遍历通常有两种方式：递归实现遍历和利用堆栈实现遍历。

2.1.2 中序遍历(左根右)

二叉树的前序遍历的步骤如下：

访问当前节点的左子树----> 访问根节点---->访问当前节点的右子树。

同样的，以上图为例，对其进行中序遍历的步骤为：

1. 按照“左根右”的顺序，先访问左子节点2，但是2还有左子节点4,4有左子节点8，而8为叶子结点，所以第1个访问的元素为8，接着访问节点8的父节点4，然后访问4的右子节点9.得到序列8、4、9。至此以4为根节点的左子树遍完毕。

2. 访问节点4的父节点2，访问其右子节点5，但是节点5有左子节点10，10为叶子节点，得到的序列为：2、10、5。至此，以2为根节点的左子树的遍历完毕，得到序列：8、4、9、2、10、5。

3. 访问整棵树的根节点1，访问其右子节点3，但其有左子节点6,6为叶子节点。所以最先访问的是6，接着访问其父节点3，再访问3的右子节点7，7为叶子节点，至此以1为根节点的右子树遍历完毕。得到序列1、6、3、7。至此整棵二叉树的遍历完毕。

得到的结果为：8、4、9、2、10、5、1、6、3、7

实现中序遍历同样有两种方式：递归实现遍历和利用堆栈实现遍历。

2.1.3 后序遍历(左右根)

二叉树的后序遍历步骤如下：

访问当前节点的左子树---->访问当前节点的右子树---->访问根节点

同样的，以上图为例，对其进行后序遍历的步骤：

1. 按照“左右根”的顺序，首先访问节点8，接着访问节点9，因为节点8和节点9都为叶子节点，所以接下来访问节点4。至此以2为根节点的左子树遍历完毕，接着遍历以2为根节点的右子树，首先访问节点10，接着访问节点5，最后访问节点2。至此，以1为根节点的左子树的遍历完毕，得到的序列为：8、9、4、10、5。

2. 遍历以1为根节点的右子树，首先访问节点6，接着访问节点7，因为节点6和节点7都是叶子节点，所以接下来访问节点3。最后访问整棵树的根节点1。至此，整棵树的遍历完毕。

得到的结果为：8、9、4、10、5、2、6、7、3、1

实现后序遍历同样有两种方式：递归实现遍历和利用堆栈实现遍历。

2.2 代码实现

class TreeNode():
    """定义树节点"""

    def __init__(self, data, left_child=None, right_child=None):
        """
        :param data: 树节点存储的数据
        :param left_child: 左子树
        :param right_child: 右子树
        """
        self.data = data
        self.left_child = left_child
        self.right_child = right_child


class BinaryTree():
    def __init__(self):
        self.root = None  # 初始化根节点为None
        self.ls = []  # 定义列表用于存储节点地址

    def add(self, data):
        """
        :param data: 要添加的数据
        :return:
        """
        node = TreeNode(data)  # 实例化树节点
        if self.root is None:  # 若根节点为None,添加根节点，并将根节点的地址添加到到self.ls中
            self.root = node
            self.ls.append(self.root)
        else:
            rootNode = self.ls[0]  # 将第一个元素设为根节点
            if rootNode.left_child is None:  # 若根节点的左孩子为None,添加左节点，并将左节点的地址添加到到self.ls中
                rootNode.left_child = node
                self.ls.append(rootNode.left_child)
            elif rootNode.right_child is None:  # 若根节点的右孩子为None,添加右节点，并将右节点的地址添加到到self.ls中
                rootNode.right_child = node
                self.ls.append(rootNode.right_child)
                self.ls.pop(0)  # 弹出self.ls中第一个元素

    def preOrderTraverse(self, root):
        """前序遍历"""
        if root is None:
            return

        print(root.data, end=" ")
        self.preOrderTraverse(root.left_child)
        self.preOrderTraverse(root.right_child)

    def InOrderTraverse(self, root):
        """中序遍历"""
        if root is None:
            return

        self.InOrderTraverse(root.left_child)
        print(root.data, end=" ")
        self.InOrderTraverse(root.right_child)

    def PostOrderTraverse(self, root):
        """后序遍历"""
        if root is None:
            return

        self.PostOrderTraverse(root.left_child)
        self.PostOrderTraverse(root.right_child)
        print(root.data, end=" ")


if __name__ == '__main__':
    tree = BinaryTree()  # 实例化树对象
    for i in range(1, 11):  # 向节点中添加元素1-10
        tree.add(i)
    print("前序遍历:", end=' ')
    tree.preOrderTraverse(tree.root)
    print()  # 换行
    print("中序遍历:", end=' ')
    tree.InOrderTraverse(tree.root)
    print()  # 换行
    print("后序遍历:", end=' ')
    tree.PostOrderTraverse(tree.root)

结果

前序遍历: 1 2 4 8 9 5 10 3 6 7 
中序遍历: 8 4 9 2 10 5 1 6 3 7 
后序遍历: 8 9 4 10 5 2 6 7 3 1 

原文链接：https://blog.csdn.net/Tonywu2018/article/details/89480282