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