Python中的树形遍历算法: 非递归实现

2023-04-11 00:00:00 算法 遍历 递归

树形遍历是指按照规则遍历树形结构中的每一个节点。常见的树形遍历方式有前序遍历、中序遍历和后序遍历。本文将介绍如何使用非递归的方式实现树形遍历算法。

我们先来看一个示例树：

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

前序遍历：1, 2, 4, 5, 3, 6, 7

中序遍历：4, 2, 5, 1, 6, 3, 7

后序遍历：4, 5, 2, 6, 7, 3, 1

非递归实现

非递归的方式实现树形遍历需要借助一个栈，栈中存储的是待访问的节点。遍历过程中将节点入栈，直到栈为空为止。具体算法流程如下：

  • 初始化一个空栈和一个空列表
  • 将根节点入栈

  • 循环执行以下步骤，直到栈为空为止：

  • 从栈中弹出一个节点，并将该节点的值添加到列表中

  • 如果该节点有右子节点，将右子节点入栈
  • 如果该节点有左子节点，将左子节点入栈

使用上文的示例树对不同的遍历方式进行非递归实现的代码如下：

前序遍历

def preorderTraversal(root):
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

中序遍历

def inorderTraversal(root):
    if not root:
        return []
    stack = []
    res = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right
    return res

后序遍历

def postorderTraversal(root):
    if not root:
        return []
    stack1 = [root]
    stack2 = []
    res = []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        res.append(stack2.pop().val)
    return res

以上代码均使用了迭代的方式实现树形遍历，相比于递归实现，它们可以更好地控制内存的使用，避免由于递归深度过大而导致的栈溢出等问题。

相关文章