开发者社区> 吞吞吐吐的> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

python 二叉树

简介:
+关注继续查看
class Node(object): def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right class BTree(object): def __init__(self, root=None): self.root = root def is_empty(self): if self.root is None: return True else: return False # 先序遍历(递归,recursion) def pre_order(self, node): if node is None: return print(node.data) self.pre_order(node.left) self.pre_order(node.right) # 中序遍历(递归) def in_order(self, node): if node is None: return self.in_order(node.left) print(node.data) self.in_order(node.right) # 后序遍历(递归) def post_order(self, node): if node is None: return self.post_order(node.left) self.post_order(node.right) print(node.data) # 先序遍历(非递归) def preorder(self, node): stack = [] while node or stack: if node is not None: print(node.data) stack.append(node) node = node.left else: node = stack.pop() node = node.right # 中序遍历(非递归) def inorder(self, node): stack = [] while node or stack: if node: stack.append(node) node = node.left else: node = stack.pop() print(node.data) node = node.right # 后序遍历(非递归) def postorder(self, node): stack = [] queue = [] queue.append(node) while queue: node = queue.pop() if node.left: queue.append(node.left) if node.right: queue.append(node.right) stack.append(node) while stack: print(stack.pop().data) # 水平遍历 def levelorder(self, node): if node is None: return queue = [node] while queue: node = queue.pop(0) print(node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 根据前序遍历和中序遍历,求后序遍历 def findTree(self, preList, midList, afterList): ''' preList = list('DBACEGF') midList = list('ABCDEFG') afterList = ['A', 'C', 'B', 'F', 'G', 'E', 'D'] ''' if len(preList)==0: return if len(preList)==1: afterList.append(preList[0]) return root = preList[0] n = midList.index(root) self.findTree(preList[1:n+1], midList[:n], afterList) self.findTree(preList[n+1:], midList[n+1:], afterList) afterList.append(root) #return afterList ''' n1 = Node(data=1) n2 = Node(2,n1,None) n3 = Node(3) n4 = Node(4) n5 = Node(5,n3,n4) n6 = Node(6,n2,n5) n7 = Node(7,n6,None) n8 = Node(8) root = Node(0,n7,n8) ''' root = Node(0, Node(7, Node(6, Node(2, Node(1)), Node(5, Node(3), Node(4)))), Node(8)) bt = BTree(root) print('pre_order......') print(bt.pre_order(bt.root)) print('in_order......') print(bt.in_order(bt.root)) print('post_order.....') print(bt.post_order(bt.root)) preList = list('DBACEGF') midList = list('ABCDEFG') afterList = [] bt.findTree(preList, midList, afterList)

print(afterList)


本文转自罗兵博客园博客,原文链接:http://www.cnblogs.com/hhh5460/p/5887332.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
python实现二叉树的创建和遍历
python实现二叉树的创建和遍历
23 0
4849
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载