黑松山资源网 Design By www.paidiu.com
本文实例讲述了python实现的二叉树定义与遍历算法。分享给大家供大家参考,具体如下:
初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构。建树的时候做了处理,保证建立的二叉树是平衡二叉树。
# -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=left self.right=right #setter and getter def get_val(self): return self.val def set_val(self,val): self.val=val def get_left(self): return self.left def set_left(self,left): self.left=left def get_right(self): return self.right def set_right(self,right): self.right=right class Tree: def __init__(self,list): list=sorted(list) self.root=self.build_tree(list) #递归建立平衡二叉树 def build_tree(self,list): l=0 r=len(list)-1 if(l>r): return None if(l==r): return Node(list[l]) mid=(l+r)/2 root=Node(list[mid]) root.left=self.build_tree(list[:mid]) root.right=self.build_tree(list[mid+1:]) return root #前序遍历 def preorder(self,root): if(root is None): return print root.val self.preorder(root.left) self.preorder(root.right) #后序遍历 def postorder(self,root): if(root is None): return self.postorder(root.left) self.postorder(root.right) print root.val #中序遍历 def inorder(self,root): if(root is None): return self.inorder(root.left) print root.val self.inorder(root.right) #层序遍历 def levelorder(self,root): if root is None: return queue =deque([root]) while(len(queue)>0): size=len(queue) for i in range(size): node =queue.popleft() print node.val if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) list=[1,-1,3,4,5] tree=Tree(list) print '中序遍历:' tree.inorder(tree.root) print '层序遍历:' tree.levelorder(tree.root) print '前序遍历:' tree.preorder(tree.root) print '后序遍历:' tree.postorder(tree.root)
输出:
中序遍历 -1 1 3 4 5 层序遍历 3 -1 4 1 5 前序遍历 3 -1 1 4 5 后序遍历 1 -1 5 4 3
建立的二叉树如下图所示:
PS:作者的github: https://github.com/zhoudayang
更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- 【原神】V5.0攻略 | 林尼攻略一图流
- 李翊君.1993-相思的烈酒【上华】【WAV+CUE】
- 古巨基.1998-LEO.KU(国)【千禧年代】【WAV+CUE】
- 郭子.2001-原来你什么都不想要创作集丫滚石】【WAV+CUE】
- 《使命召唤:黑色行动6》新预告公布!10月25日发售
- Atlus《暗喻幻想》媒体评分汇总:高分好评如潮!
- 2024金摇杆奖提名揭晓 《黑神话》角逐最佳视觉设计!
- 群星《新说唱2024 第3期 (上)》[320K/MP3][32.76MB]
- 群星《新说唱2024 第3期 (上)》[FLAC/分轨][95.38MB]
- 群星《新说唱2024 第3期 (下)》[320K/MP3][31.36MB]
- 幻兽帕鲁手游什么时候正式上线 最新消息一览
- 西普大陆BOSS位置盘点 解锁天启纪元玩法
- 西普大陆精灵进阶培养攻略 精灵养成指南
- dnf手游法控法系职业哪个强 dnf手游法控法系职业强度排行
- 魔兽世界血藤护目镜图纸在哪买 wlk血藤护目镜图纸购买位置介绍