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

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

2020-12-20 00:48caochao Python

这篇文章主要介绍了Python二叉树的定义及常用遍历算法,结合实例形式分析了基于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 )