# coding:utf-8

class Node(object):     """docstring for Node"""

    def __init__(self, item=-1, lchild=None, rchild=None):

        self.item = item         self.lchild = lchild         self.rchild = rchild

class Tree(object):     """docstring for Tree"""

    def __init__(self):

        self.root = Node()

    def add(self, item):

        '''         添加一个节点         顺序:从上至下，从左至右.         '''         node = Node(item)

        if self.root.item == -1:

            self.root = node         else:             myqueue = []             tree_node = self.root             myqueue.append(tree_node)

            while myqueue:

                tree_node = myqueue.pop(0)                 if not tree_node.lchild:                     # 左孩子空，添加到左孩子.                     tree_node.lchild = node                     return                 elif not tree_node.rchild:                     tree_node.rchild = node                     return                 else:                     # 若左右都不为空，加入该节点的左右孩子到列表                     myqueue.append(tree_node.lchild)                     myqueue.append(tree_node.rchild)

    def front(self, root=None):

        if not root:             return         print(root.item)         self.front(root.lchild)         self.front(root.rchild)

    def middle(self, root=None):

        if not root:             return         self.middle(root.lchild)         print(root.item)         self.middle(root.rchild)

    def later(self, root=None):

        if not root:             return         self.later(root.lchild)         self.later(root.rchild)         print(root.item)

    def level_search(self, root):

        '''         从上至下，从左至右.         '''         if not root:             return

        myQueue = []

        node = root         myQueue.append(node)

        while myQueue:

            tree_node = myQueue.pop(0)             print(tree_node.item)

            if tree_node.lchild:

                myQueue.append(tree_node.lchild)

            if tree_node.rchild:

                myQueue.append(tree_node.rchild)

def main():     tree = Tree()     for i in xrange(7):         tree.add(i)

    # tree.front(tree.root)

    # 0 1 3 4 2 5 6     # tree.middle(tree.root)     # 3 1 4 0 5 2 6     # tree.later(tree.root)     #3, 4, 1, 5, 6, 2, 0     tree.level_search(tree.root)     # 0 1 2 3 4 5 6

if __name__ == '__main__':

    main()

##########################

#             0 #     1       |     2 # 3       4   |  5      6 ##########################