python实现的二叉树定义与遍历算法实例
发布于 2017-10-27 23:06:03 | 153 次阅读 | 评论: 0 | 来源: 网友投递
Python编程语言
Python 是一种面向对象、解释型计算机程序设计语言，由Guido van Rossum于1989年底发明，第一个公开发行版发行于1991年。Python语法简洁而清晰，具有丰富和强大的类库。它常被昵称为胶水语言，它能够把用其他语言制作的各种模块（尤其是C/C++）很轻松地联结在一起。
这篇文章主要介绍了python实现的二叉树定义与遍历算法,结合具体实例形式分析了基于Python定义的二叉树及其常用遍历操作实现技巧,需要的朋友可以参考下
本文实例讲述了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程序设计有所帮助。
推荐阅读
最新资讯