Python二叉树的定义及常用遍历算法分析

时间:2022-06-01 06:13:19

本文实例讲述了Python二叉树的定义及常用遍历算法。分享给大家供大家参考,具体如下:

说起二叉树的遍历,大学里讲的是递归算法,大多数人首先想到也是递归算法。但作为一个有理想有追求的程序员。也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开。

以下直入主题:

定义一颗二叉树,请看官自行想象其形状,

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

先序遍历:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
'''
先序遍历二叉树
'''
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 )

中序遍历:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
'''
中序遍历二叉树
'''
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

后序遍历:

后序遍历中,要保证左孩子和右孩子都已被访问才能访问根结点,并且左孩子需在右孩子前访问,这就为流程的控制带来了难题。下面介绍两种思路。

思路一,双栈法,这种方式比较容易理解,缺点是需要两个栈。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
后序遍历二叉树
'''
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的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 )

层序遍历:

?
1
2
3
4
5
6
7
8
9
10
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程序设计有所帮助。

原文链接:https://www.cnblogs.com/tudas/p/binary-tree-traverse.html