Python二叉树定义与遍历方法实例分析
本文实例讲述了Python二叉树定义与遍历方法。分享给大家供大家参考,具体如下:
二叉树基本概述:
二叉树是有限个元素的几个,如果为空则为空二叉树,或者有一个结点称之为根节点,分列根节点两侧的为二叉树的左右子节点,二叉树有如下的性质:
1. 二叉树的每个结点不存在度大于2的结点
2. 二叉树的第i层至多有2^{i-1}个结点
3. 深度为k的二叉树至多有2^k - 1个结点
4. 二叉树中,度为0的结点数N0比度为2的结点数N2大1,即存在N2 + 1 = N0
Python代码:
#coding:utf-8 'BiTree' class Node(object): 'Node Defination' def __init__(self,item): self.item = item self.left = None self.right = None class Tree(object): 'Bitree Defination' def __init__(self): self.root = None def add(self,item): node = Node(item) if self.root is None: self.root = node else: q = [self.root] while True: pop_node = q.pop(0) if pop_node.left is None: pop_node.left = node return elif pop_node.right is None: pop_node.right = node return else: q.append(pop_node.left) q.append(pop_node.right) def traverse(self):#层次遍历 if self.root is None: return None q = [self.root] res = [self.root.item] while q != []: pop_node = q.pop(0) if pop_node.left is not None: q.append(pop_node.left) res.append(pop_node.left.item) if pop_node.right is not None: q.append(pop_node.right) res.append(pop_node.right.item) return res def preorder(self,root): #先序遍历 if root is None: return [] result = [root.item] left_item = self.preorder(root.left) right_item = self.preorder(root.right) return result + left_item + right_item def inorder(self,root): #中序遍历 if root is None: return [] result = [root.item] left_item = self.inorder(root.left) right_item = self.inorder(root.right) return left_item + result + right_item def postorder(self,root): #后序遍历 if root is None: return [] result = [root.item] left_item = self.postorder(root.left) right_item = self.postorder(root.right) return left_item + right_item + result if __name__=='__main__': t = Tree() for i in range(10): t.add(i) print "层序遍历:",t.traverse() print "先序遍历:",t.preorder(t.root) print "中序遍历:",t.inorder(t.root) print "后序遍历:",t.postorder(t.root)
输出结果:
层序遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先序遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中序遍历: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后序遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]
这里对于
if __name__=='__main__': “Make a script both importable and executable”
意思就是说让你写的脚本模块既可以导入到别的模块中用,另外该模块自己也可执行。
这里通过一个示例进行解释:
#test.py def func(): print "we are in %s"%__name__ if __name__ == '__main__': func()
输出结果:
we are in __main__
说明if语句中的内容被执行了,调用了 func()
函数,现在在另一个模块中调用func函数
#testtest from test import func func()
输出结果:
we are in moudle
也就是说 if 条件中的内容没有执行。
总结:
如果直接执行某个*.py文件,该文件中 if __name__ == '__main__'
是True,相当于调式本模块的代码;如果是从另一个模块(testtest.py)通过import导入该文件的时候,这时__name__就是这个模块的名字(test)而不是__main__,总之在调式代码的时候加上 if __name__ == '__main__'
中加入调试代码,可以让步模块调用的时候不执行调式代码,如果想排查本模块代码的问题时,直接进行调试执行
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。