Python二叉树定义与非递归遍历算法详解

南乔

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

原创

本文深入解析Python中二叉树的定义及非递归遍历算法。通过辅助栈结构，详细阐述先序、中序、后序（含双栈法与单栈法）及层序遍历的实现逻辑。文章提供完整代码示例，展示如何利用栈和队列解决递归替代问题，适用于数据结构学习与算法优化参考。

本文通过具体实例，详细解析Python中二叉树的基本定义以及几种常用的遍历算法，旨在为读者提供清晰的参考与学习素材。

在讨论二叉树遍历时，大学教材通常侧重于递归算法，这也是大多数开发者首先掌握的方法。然而，对于追求技术深度的程序员而言，掌握非递归算法同样重要。非递归实现依赖于辅助栈，其设计思路巧妙且极具启发性，能够有效拓展编程思维。

接下来直接进入核心内容。

首先定义一个二叉树节点结构，具体的树形结构由读者根据后续代码自行构建。

class BinNode( ):
  def __init__( self, val ):
    self.lchild = None
    self.rchild = None
    self.value = val
binNode1 = BinNode( 1 )
binNode2 = BinNode( 2 )
binNode3 = BinNode( 3 )
binNode4 = BinNode( 4 )
binNode5 = BinNode( 5 )
binNode6 = BinNode( 6 )
binNode1.lchild = binNode2
binNode1.rchild = binNode3
binNode2.lchild = binNode4
binNode2.rchild = binNode5
binNode3.lchild = binNode6

先序遍历的实现逻辑如下：

'''
先序遍历二叉树
'''
def bin_tree_pre_order_traverse( root, visit_func ):
  s = Stack()
  s.push( root )
  while not s.is_empty():
    node = s.pop()
    visit_func( node )
    if node.rchild:
      s.push( node.rchild )
    if node.lchild:
      s.push( node.lchild )

中序遍历的实现逻辑如下：

'''
中序遍历二叉树
'''
def bin_tree_in_order_traverse( root, visit_func ):
  s = Stack()
  node = root
  while node or not s.is_empty():
    if node:
      s.push( node )
      node = node.lchild
    else:
      node = s.pop()
      visit_func( node )
      node = node.rchild

后序遍历的实现逻辑如下：

在后序遍历中，必须确保左子树和右子树均被访问完毕后，才能访问根节点，且左子树的访问顺序需优先于右子树。这一约束增加了流程控制的复杂性，下文将介绍两种解决思路。

第一种思路采用双栈法，该方法逻辑直观，易于理解，但主要缺点是需要消耗两个栈的空间。

'''
后序遍历二叉树
'''
def bin_tree_post_order_traverse( root, visit_func ):
  s1 = Stack()
  s2 = Stack()
  s1.push( root )
  while not s1.is_empty():
    node = s1.pop()
    s2.push( node )
    if node.lchild:
      s1.push( node.lchild )
    if node.rchild:
      s1.push( node.rchild )
  while not s2.is_empty():
    visit_func( s2.pop() )

第二种思路旨在确保根节点在左右孩子访问之后才被处理。具体做法是：先将当前节点P入栈。若P无左右孩子，或虽有孩子但均已访问过，则直接访问P；否则，将P的右孩子和左孩子依次入栈。这样能保证栈顶元素取出时，左孩子在右孩子之前被访问，且左右孩子均在根节点之前被处理。

def bin_tree_post_order_traverse2( root, visit_func ):
  curr = root
  prev = None
  s = Stack()
  s.push( curr )
  while not s.is_empty():
    curr = s.peek()
    if ( not curr.lchild and not curr.rchild ) or ( prev and ( prev == curr.lchild or prev == curr.rchild ) ):
      visit_func( curr )
      s.pop()
　　　　　　　prev = curr
    else:
      if curr.rchild:
        s.push( curr.rchild )
      if curr.lchild:
        s.push( curr.lchild )

层序遍历的实现逻辑如下：

def bin_tree_level_traverse( root, visit_func ):
  queue = Queue()
  queue.enqueue( root )
  while not queue.is_empty():
    node = queue.dequeue().value
    visit_func( node )
    if node.lchild:
      queue.enqueue( node.lchild )
    if node.rchild:
      queue.enqueue( node.rchild )

如需了解更多Python相关技术，可参考本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》。

希望上述内容能对您的Python程序设计学习有所帮助。