二叉树的递归遍历及非递归遍历

最近在复习二叉树的相关内容，这里将二叉树的三种常规遍历的递归形式和非递归形式总结一下。

三种遍历的规则如下：

• 前序遍历：根节点->左⼦树->右⼦树
• 中序遍历：左⼦树->根节点->右⼦树
• 后序遍历：左⼦树->右⼦树->根节点

可以看到：前序、中序、后序均是针对根节点而言，另外左子树总数先于右子树。

构建二叉树

class BinaryTree:
    def __init__(self):
        self.root = None
    def _add(self, item):
        """广度优先遍历方式添加节点"""
        if self.root is None:
            self.root = Node(item)
        else:
            queue = list()
            queue.append(self.root)

            while len(queue) > 0:
                node = queue.pop(0)
                if not node.left:
                    node.left = Node(item)
                    return
                else:
                    queue.append(node.left)
                if not node.right:
                    node.right = Node(item)
                    return
                else:
                    queue.append(node.right)

    @property
    def header(self):
        return self.root

    def add(self,arr):
        for i in arr:
            self._add(i)

本文构造如下二叉树：

             1
          /   \
        2      3
      /  \    /  \
     4    5  6    7
    / \
  8    9

前序遍历

def preoder(root):
    stack = []
    outlist = []
    while stack or root:
        while root:
            outlist.append(root.val)
            stack.append(root)
            root = root.left
        root = stack.pop()
        root = root.right
    return outlist

验证：

# 构建二叉树
arr = [1,2,3,4,5,6,7,8,9]
tree = BinaryTree()
tree.add(arr)
# 前序遍历
print(preoder(tree.header))

输出：

[1, 2, 4, 8, 9, 5, 3, 6, 7]

中序遍历

def inorder(root):
    stack = []
    outlist = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        outlist.append(root.val)
        root = root.right
    return outlist

验证：

# 构建二叉树
arr = [1,2,3,4,5,6,7,8,9]
tree = BinaryTree()
tree.add(arr)
# 中序遍历
print(inorder(tree.header))

输出：

[8, 4, 9, 2, 5, 1, 6, 3, 7]

后序遍历

def postorder(root):
    stack = []
    outlist = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left if root.left else root.right
        root = stack.pop()
        outlist.append(root.val)
        if stack and stack[-1].left == root:
            root = stack[-1].right
        else:
            root = None
    return outlist

验证：

# 构建二叉树
arr = [1,2,3,4,5,6,7,8,9]
tree = BinaryTree()
tree.add(arr)
# 后序遍历
print(postorder(tree.header))

输出：

[8, 9, 4, 5, 2, 6, 7, 3, 1]