python实现的二叉树定义与遍历算法实例

# -*- coding: utf-8 -*-from collections import dequeclass 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=rightclass 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)

中序遍历-11345层序遍历3-1415前序遍历3-1145后序遍历1-1543