"""
二叉树
"""


class Node(object):
    """
    树的节点
    """
    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.Rchild = None

class Tree(object):
    """
    二叉树
    """
    def __init__(self):
        """
        弄一个根节点
        """
        self.root = None

    def add(self, item):
        """队列查找广度优先"""
        node = Node(item)
        if self.root is None:
            self.root = node
            return

        queue = []
        queue.append(self.root)

        # 先从队列中取出一个节点(要循环,只要列表里面有值，就可以一直判断下去)
        # 从上往下，从左到右挂节点
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                break
            else:
                queue.append(cur_node.lchild)

            if cur_node.Rchild is None:
                cur_node.Rchild = node
                break
            else:
                queue.append(cur_node.Rchild)
        
    def travel_broaden(self):
        """广度优先遍历"""
        if self.root is None:
            return

        queue = [self.root]
        c = 0
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem)
            if cur_node.lchild != None:
                queue.append(cur_node.lchild) 
            
            if cur_node.Rchild != None:
                queue.append(cur_node.Rchild)
    
    def prepro(self, node):
        """先序遍历(根左右)"""
        if node == None:
            return
        print(node.elem)

        self.prepro(node.lchild)
        self.prepro(node.Rchild)
    
    def inorder(self, node):
        """中序排序(左根右)"""
        if node == None:
            return

        self.inorder(node.lchild)
        print(node.elem)
        self.inorder(node.Rchild)
    
    def postoder(self, node):
        """后续排序(左右根)"""
        if node == None:
            return

        self.postoder(node.lchild)
        self.postoder(node.Rchild)
        print(node.elem)
    
if __name__ == '__main__':
    t = Tree()
    for i in range(10):
        t.add(i)
    t.postoder(t.root)