本来打算一个学期分别用C++、Python、Java实现数据结构，看来要提前了

这个是Python版本，我写的数据结构尽量保持灵活性，本文bt1是一般的插入法建立二叉树结构，bt2就是可以任意输入，至于树的高度的递归和非递归实现等等，在C++里实现过就不再重复。

#Date     : 2013-9-12

#Author   : DVD0423

#Function : 二叉树

class Node:

    def __init__(self, value = None, left = None, right = None):

        self.value = value

        self.left = left

        self.right = right

    def visit(self):

        print(self.value)

class BTree:

    def __init__(self, root = Node()):

        self.root = root

    def CreateBTree(self, _list = []):

        #层序遍历，产生二叉树结构

        length = len(_list)

        node = []

        for i in range(length):

            node.append(Node())

            node[i].value = _list[i]

        front = 0

        rear = 0

        while(rear != length):

            rear = rear + 1

            if rear >= length:

                break

            node[front].left = node[rear]

            rear = rear + 1

            if rear >= length:

                break

            node[front].right = node[rear]

            front = front + 1

        #下面这句没有必要，因为初始化就是None,但是逻辑上要有

        while(front != length):

            node[front].left = None

            node[front].right = None

            front = front + 1

        self.root = node[0]

    def Traverse(self, method):

        def PostOrder(node):

            if node:

                PostOrder(node.left)

                PostOrder(node.right)

                node.visit()

        def InOrder(node):

            if node:

                InOrder(node.left)

                node.visit()

                InOrder(node.right)

        def PreOrder(node):

            if node:

                node.visit()

                PreOrder(node.left)

                PreOrder(node.right)

        def NoRecTraverse(node):

            ls = []

            while True:

                if node:

                    ls.append(node)

                    node.visit()

                    node = node.left

                else:

                    if len(ls) != 0:

                        node = ls.pop()

                    node = node.right

                    if len(ls) == 0 and node == None:

                        break

        if method is 1:

            print("后序遍历")

            PostOrder(self.root)

        elif method is 2:

            print("中序遍历")

            InOrder(self.root)

        elif method is 3:

            print("前序遍历")

            PreOrder(self.root)

        else:

            print("非递归先序遍历")

            NoRecTraverse(self.root)

def InputInt():

    seq = []

    while True:

        ch = input()

        if ch is 'e':

            break

        seq.append(int(ch))

    return seq    

if __name__ == '__main__':

    #两种方式建立二叉树

    print("二叉树1：")

    node3 = Node(3)

    node2 = Node(2)

    node1 = Node(1, node2, node3)

    bt1 = BTree(node1)

    bt1.Traverse(4)

    print("二叉树2：")

    ls = InputInt()

    bt2 = BTree()

    bt2.CreateBTree(ls)

    bt2.Traverse(4)