分享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