黑松山资源网 Design By www.paidiu.com
本文实例讲述了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程序设计有所帮助。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月11日
2024年10月11日
- 邰肇玫.1981-雪歌(滚石25周年经典复刻系列)【滚石】【WAV+CUE】
- 《Duck Side of the Moon》特色玩法介绍
- 《刀郎 辉煌10年绝版珍藏 3CD》[WAV/分轨][1.6GB]
- 《张韶涵 全面沦陷》[WAV/分轨][370MB]
- 《极品汽车音乐 三十而立 一起走过的岁月 2CD》[WAV/分轨][990MB]
- 周冰倩1997-珍藏精选-真的好想你[WAV+CUE]
- 许廷铿2017《THEULTIMATECOLLECTION》2CD[星梦娱乐][WAV+CUE]
- 徐小明1983-再向虎山行(LP版)[文志][WAV+CUE]
- 《黑神话:悟空》石双双COS热潮持续升温 丝袜你喜欢么
- Qiddiya IRL游戏之旅在东京电玩展重磅登场
- 北京首家任天堂Switch体验店开业:国行机立减200元
- 张秀卿.1999-赢【神采】【WAV+CUE】
- 群星.1977-多多宝丽多(LP版)【宝丽金】【WAV+CUE】
- 刘德华.1989-永远...记得你(2012金碟复刻版)【EMI百代】【WAV+CUE】
- 《维纳斯璀璨假期死或生Xtreme》游戏特色玩法