Python二叉树的定义及常用遍历算法分析
本文实例讲述了Python二叉树的定义及常用遍历算法。分享给大家供大家参考，具体如下：
说起二叉树的遍历，大学里讲的是递归算法，大多数人首先想到也是递归算法。但作为一个有理想有追求的程序员。也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈，算法着实巧妙，令人脑洞大开。
以下直入主题：
定义一颗二叉树，请看官自行想象其形状，
classBinNode(): 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
先序遍历：
''' 先序遍历二叉树 ''' defbin_tree_pre_order_traverse(root,visit_func): s=Stack() s.push(root) whilenots.is_empty(): node=s.pop() visit_func(node) ifnode.rchild: s.push(node.rchild) ifnode.lchild: s.push(node.lchild)
中序遍历：
''' 中序遍历二叉树 ''' defbin_tree_in_order_traverse(root,visit_func): s=Stack() node=root whilenodeornots.is_empty(): ifnode: s.push(node) node=node.lchild else: node=s.pop() visit_func(node) node=node.rchild
后序遍历：
后序遍历中，要保证左孩子和右孩子都已被访问才能访问根结点，并且左孩子需在右孩子前访问，这就为流程的控制带来了难题。下面介绍两种思路。
思路一，双栈法，这种方式比较容易理解，缺点是需要两个栈。
''' 后序遍历二叉树 ''' defbin_tree_post_order_traverse(root,visit_func): s1=Stack() s2=Stack() s1.push(root) whilenots1.is_empty(): node=s1.pop() s2.push(node) ifnode.lchild: s1.push(node.lchild) ifnode.rchild: s1.push(node.rchild) whilenots2.is_empty(): visit_func(s2.pop())
思路二，要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
defbin_tree_post_order_traverse2(root,visit_func): curr=root prev=None s=Stack() s.push(curr) whilenots.is_empty(): curr=s.peek() if(notcurr.lchildandnotcurr.rchild)or(prevand(prev==curr.lchildorprev==curr.rchild)): visit_func(curr) s.pop() prev=curr else: ifcurr.rchild: s.push(curr.rchild) ifcurr.lchild: s.push(curr.lchild)
层序遍历：
defbin_tree_level_traverse(root,visit_func): queue=Queue() queue.enqueue(root) whilenotqueue.is_empty(): node=queue.dequeue().value visit_func(node) ifnode.lchild: queue.enqueue(node.lchild) ifnode.rchild: queue.enqueue(node.rchild)
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。