首页 > 代码库 > python实现二叉树遍历算法
python实现二叉树遍历算法
说起二叉树的遍历，大学里讲的是递归算法，大多数人首先想到也是递归算法。但作为一个有理想有追求的程序员。也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈，算法着实巧妙，令人脑洞大开。
以下直入主题：
定义一颗二叉树，请看官自行想象其形状，
class BinNode( ): def __init__( self, val ): self.lchild = None self.rchild = None self.value = valbinNode1 = BinNode( 1 )binNode2 = BinNode( 2 )binNode3 = BinNode( 3 )binNode4 = BinNode( 4 )binNode5 = BinNode( 5 )binNode6 = BinNode( 6 )binNode1.lchild = binNode2binNode1.rchild = binNode3binNode2.lchild = binNode4binNode2.rchild = binNode5binNode3.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() )
层序遍历：
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实现二叉树遍历算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。