Python 递归式实现二叉树前序,中序,后序遍历

Python递归式实现二叉树前序、中序、后序遍历

在二叉树中，前序、中序、后序遍历是常用的遍历方式。其中，前序遍历的顺序是先遍历根节点，然后遍历其左子树，最后遍历其右子树（根-左-右）；中序遍历的顺序是先遍历左子树，再遍历根节点，最后遍历右子树（左-根-右）；后序遍历的顺序是先遍历左子树，再遍历右子树，最后遍历根节点（左-右-根）。Python可以用递归的方式实现这三种遍历方式。

实现步骤

1.定义二叉树节点类

class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

2.定义二叉树类

class BinaryTree(object):
    def __init__(self):
        self.root = None

3.实现三种遍历方式

#前序遍历
def preorder_traversal(self, node):
    if node is not None:
        print(node.val, end=" ")
        self.preorder_traversal(node.left)
        self.preorder_traversal(node.right)
#中序遍历
def inorder_traversal(self, node):
    if node is not None:
        self.inorder_traversal(node.left)
        print(node.val, end=" ")
        self.inorder_traversal(node.right)
#后序遍历
def postorder_traversal(self, node):
    if node is not None:
        self.postorder_traversal(node.left)
        self.postorder_traversal(node.right)
        print(node.val, end=" ")

其中，node为二叉树节点。

示例

下面我们来看两个二叉树的前序、中序、后序遍历结果。

例1：输入如下二叉树

    1
  /   \
2      3

则出现以下结果：

tree = BinaryTree()
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
print("前序遍历:", end=" ")
tree.preorder_traversal(tree.root)
print("\n中序遍历:", end=" ")
tree.inorder_traversal(tree.root)
print("\n后序遍历:", end=" ")
tree.postorder_traversal(tree.root)

输出：

前序遍历: 1 2 3 
中序遍历: 2 1 3 
后序遍历: 2 3 1

例2：输入如下二叉树

    5  
   / \  
  3   8  
 / \   \  
1   4   10

则出现以下结果：

tree = BinaryTree()
tree.root = TreeNode(5)
tree.root.left = TreeNode(3)
tree.root.right = TreeNode(8)
tree.root.left.left = TreeNode(1)
tree.root.left.right = TreeNode(4)
tree.root.right.right = TreeNode(10)
print("前序遍历:", end=" ")
tree.preorder_traversal(tree.root)
print("\n中序遍历:", end=" ")
tree.inorder_traversal(tree.root)
print("\n后序遍历:", end=" ")
tree.postorder_traversal(tree.root)

输出：

前序遍历: 5 3 1 4 8 10 
中序遍历: 1 3 4 5 8 10 
后序遍历: 1 4 3 10 8 5