Python二叉树构建与全遍历算法详解：递归与非递归实现

晚来风

发布时间：2026-10-13| 6人浏览过

原创

本文详细解析Python中二叉树的构建与四种核心遍历算法。通过递归与非递归两种方式，分别实现前序、中序、后序及层次遍历。重点阐述利用栈结构处理非递归遍历时节点入栈与出栈的逻辑，以及后序遍历中双栈法的应用，附带完整代码与运行结果分析，帮助开发者深入理解树形数据结构的操作细节。

二叉树数据结构概述

树和图这类数据结构在计算机科学中极具研究价值，其逻辑结构复杂且应用广泛。


# coding = utf-8

 

 

class BinaryTree:

  def __init__(self, root_obj):

    self.key = root_obj

    self.left_child = None

    self.right_child = None

 

  def insert_left(self, new_node):

    node = BinaryTree(new_node)

    if self.left_child is None:

      self.left_child = node

    else:

      node.left_child = self.left_child

      self.left_child = node

 

  def insert_right(self, new_node):

    node = BinaryTree(new_node)

    if self.right_child is None:

      self.right_child = node

    else:

      node.right_child = self.right_child

      self.right_child = node

 

  def get_right_child(self):

    return self.right_child

 

  def get_left_child(self):

    return self.left_child

 

  def set_root_val(self, obj):

    self.key = obj

 

  def get_root_val(self):

    return self.key

 

 

root = BinaryTree('a')

print(root.get_root_val())

print(root.get_left_child())

root.insert_left('b')

print(root.get_left_child())

print(root.get_left_child().get_root_val())

root.insert_right('c')

print(root.get_right_child())

print(root.get_right_child().get_root_val())

root.get_right_child().set_root_val('hello')

print(root.get_right_child().get_root_val())


C:\Users\Sahara\.virtualenvs\test\Scripts\python.exe C:/Users/Sahara/PycharmProjects/test/python_search.py

a

None

<__main__.BinaryTree object at 0x00000000024139B0>

b

<__main__.BinaryTree object at 0x00000000024139E8>

c

hello

 

Process finished with exit code 0

Python二叉树遍历算法实现

在Python中实现二叉树的遍历，既可以使用递归算法，也可以采用非递归算法，两者各有优劣。

前序遍历：递归与非递归

前序遍历是二叉树遍历的基础方式之一，其访问顺序为根节点、左子树、右子树。


 # -----------前序遍历 ------------
  # 递归算法
  def pre_order_recursive(self, T):
    if T == None:
      return
    print(T.root, end=' ')
    self.pre_order_recursive(T.lchild)
    self.pre_order_recursive(T.rchild)

  # 非递归算法
  def pre_order_non_recursive(self, T):
    """借助栈实现前驱遍历
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        print(T.root, end=' ')
        T = T.lchild
      else:
        T = stack[-1]
        stack.pop()
        T = T.rchild

中序遍历：递归与非递归

中序遍历遵循左子树、根节点、右子树的访问顺序，对于二叉搜索树而言，中序遍历可得到有序序列。


# -----------中序遍历 ------------
  # 递归算法
  def mid_order_recursive(self, T):
    if T == None:
      return
    self.mid_order_recursive(T.lchild)
    print(T.root, end=' ')
    self.mid_order_recursive(T.rchild)

  # 非递归算法
  def mid_order_non_recursive(self, T):
    """借助栈实现中序遍历
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        T = T.lchild
      else:
        T = stack.pop()
        print(T.root, end=' ')
        T = T.rchild

后序遍历：递归与非递归

后序遍历要求先访问左子树，再访问右子树，最后访问根节点，常用于删除节点或计算目录大小等场景。


# -----------后序遍历 ------------
  # 递归算法
  def post_order_recursive(self, T):
    if T == None:
      return
    self.post_order_recursive(T.lchild)
    self.post_order_recursive(T.rchild)
    print(T.root, end=' ')

  # 非递归算法
  def post_order_non_recursive(self, T):
    """借助两个栈实现后序遍历
    """
    if T == None:
      return
    stack1 = []
    stack2 = []
    stack1.append(T)
    while stack1:
      node = stack1.pop()
      if node.lchild:
        stack1.append(node.lchild)
      if node.rchild:
        stack1.append(node.rchild)
      stack2.append(node)
    while stack2:
      print(stack2.pop().root, end=' ')
    return

层次遍历实现

层次遍历即广度优先搜索（BFS），按层级从上到下、从左到右依次访问节点。


# -----------层次遍历 ------------
  def level_order(self, T):
    """借助队列（其实还是一个栈）实现层次遍历
    """
    if T == None:
      return
    stack = []
    stack.append(T)
    while stack:
      node = stack.pop(0) # 实现先进先出
      print(node.root, end=' ')
      if node.lchild:
        stack.append(node.lchild)
      if node.rchild:
        stack.append(node.rchild)

完整代码与运行结果分析

以下是实现上述遍历逻辑的完整Python代码，包含二叉树类定义及各类遍历方法的实现。


class NodeTree:
  def __init__(self, root=None, lchild=None, rchild=None):
    """创建二叉树
    Argument:
      lchild: BinTree
        左子树
      rchild: BinTree
        右子树

    Return:
      Tree
    """
    self.root = root
    self.lchild = lchild
    self.rchild = rchild


class BinTree:

  # -----------前序遍历 ------------
  # 递归算法
  def pre_order_recursive(self, T):
    if T == None:
      return
    print(T.root, end=' ')
    self.pre_order_recursive(T.lchild)
    self.pre_order_recursive(T.rchild)

  # 非递归算法
  def pre_order_non_recursive(self, T):
    """借助栈实现前驱遍历
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        print(T.root, end=' ')
        T = T.lchild
      else:
        T = stack[-1]
        stack.pop()
        T = T.rchild

  # -----------中序遍历 ------------
  # 递归算法
  def mid_order_recursive(self, T):
    if T == None:
      return
    self.mid_order_recursive(T.lchild)
    print(T.root, end=' ')
    self.mid_order_recursive(T.rchild)

  # 非递归算法
  def mid_order_non_recursive(self, T):
    """借助栈实现中序遍历
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        T = T.lchild
      else:
        T = stack.pop()
        print(T.root, end=' ')
        T = T.rchild

  # -----------后序遍历 ------------
  # 递归算法
  def post_order_recursive(self, T):
    if T == None:
      return
    self.post_order_recursive(T.lchild)
    self.post_order_recursive(T.rchild)
    print(T.root, end=' ')

  # 非递归算法
  def post_order_non_recursive(self, T):
    """借助两个栈实现后序遍历
    """
    if T == None:
      return
    stack1 = []
    stack2 = []
    stack1.append(T)
    while stack1:
      node = stack1.pop()
      if node.lchild:
        stack1.append(node.lchild)
      if node.rchild:
        stack1.append(node.rchild)
      stack2.append(node)
    while stack2:
      print(stack2.pop().root, end=' ')
    return

  # -----------层次遍历 ------------
  def level_order(self, T):
    """借助队列（其实还是一个栈）实现层次遍历
    """
    if T == None:
      return
    stack = []
    stack.append(T)
    while stack:
      node = stack.pop(0) # 实现先进先出
      print(node.root, end=' ')
      if node.lchild:
        stack.append(node.lchild)
      if node.rchild:
        stack.append(node.rchild)

  # ----------- 前序遍历序列、中序遍历序列 —> 重构二叉树 ------------
  def tree_by_pre_mid(self, pre, mid):
    if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
      return
    T = NodeTree(pre[0])
    index = mid.index(pre[0])
    T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
    T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
    return T

  # ----------- 后序遍历序列、中序遍历序列 —> 重构二叉树 ------------
  def tree_by_post_mid(self, post, mid):
    if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
      return
    T = NodeTree(post[-1])
    index = mid.index(post[-1])
    T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
    T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
    return T


if __name__ == '__main__':
  # ----------- 测试：前序、中序、后序、层次遍历 -----------
  # 创建二叉树
  nodeTree = NodeTree(1,
            lchild=NodeTree(2,
                    lchild=NodeTree(4,
                            rchild=NodeTree(7))),
            rchild=NodeTree(3,
                    lchild=NodeTree(5),
                    rchild=NodeTree(6)))
  T = BinTree()
  print('前序遍历递归\t')
  T.pre_order_recursive(nodeTree) # 前序遍历-递归
  print('\n')
  print('前序遍历非递归\t')
  T.pre_order_non_recursive(nodeTree) # 前序遍历-非递归
  print('\n')
  print('中序遍历递归\t')
  T.mid_order_recursive(nodeTree) # 中序遍历-递归
  print('\n')
  print('中序遍历非递归\t')
  T.mid_order_non_recursive(nodeTree) # 中序遍历-非递归
  print('\n')
  print('后序遍历递归\t')
  T.post_order_recursive(nodeTree) # 后序遍历-递归
  print('\n')
  print('后序遍历非递归\t')
  T.post_order_non_recursive(nodeTree) # 后序遍历-非递归
  print('\n')
  print('层次遍历\t')
  T.level_order(nodeTree) # 层次遍历
  print('\n')

  print('==========================================================================')

  # ----------- 测试：由遍历序列构造二叉树 -----------
  T = BinTree()
  pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
  mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
  post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']

  newT_pre_mid = T.tree_by_pre_mid(pre, mid) # 由前序序列、中序序列构造二叉树
  T.post_order_recursive(newT_pre_mid) # 获取后序序列
  print('\n')

  newT_post_mid = T.tree_by_post_mid(post, mid) # 由后序序列、中序序列构造二叉树
  T.pre_order_recursive(newT_post_mid) # 获取前序序列

运行上述代码后，控制台将输出各遍历算法处理特定二叉树结构后的节点访问序列，用于验证算法正确性。

前序遍历递归执行的结果序列为：1 2 4 7 3 5 6，该序列反映了根节点优先访问的特性。

前序遍历非递归实现同样输出：1 2 4 7 3 5 6，通过显式栈模拟递归调用栈，确保访问顺序一致。

中序遍历递归执行的结果序列为：4 7 2 1 5 3 6，体现了左子树节点先于根节点被访问的规律。

中序遍历非递归实现的结果序列为：4 7 2 1 5 3 6，利用栈保存路径上的节点，待左子树处理完毕后回溯访问根节点。

后序遍历递归执行的结果序列为：7 4 2 5 6 3 1，根节点在最后被访问，符合后序遍历定义。

后序遍历非递归实现的结果序列为：7 4 2 5 6 3 1，通常需借助两个栈或标记位来区分左右子树的访问状态。

层次遍历的结果序列为：1 2 3 4 5 6 7，按层级顺序依次输出节点值，常用于图的广度优先搜索。

根据前序序列 'C B E H G I F D A' 与中序序列 'A B C D E F G H I' 构建的二叉树，其后序遍历输出为 'C B E H G I F D A'（注：此处原文输出似有重复或特定结构，依原文保留），而前序构建的节点访问顺序为 'A B C D E F G H I'，展示了序列重构二叉树的过程。

由后序序列 'C B E H G I F D A' 和中序序列构建的二叉树，其前序遍历输出为 'A B C D E F G H I'，验证了不同序列组合对树结构的唯一确定性及遍历的一致性。

综上所述，本文涵盖了二叉树的核心遍历算法及其Python实现，希望这些内容能为读者的学习提供实质性帮助，也欢迎持续关注本站以获取更多技术分享。