使用插入数据的方法构造一颗二叉树

"""
二叉搜索树定义：
    1,每个节点上都有数据
    2,当前节点的左节点数据比当前节点的数据小，并且当前节点的所有左节点数据都比当前节点的数据小
    3,当前节点的右节点数据比当前节点的数据大，并且当前节点的所有右节点数据都比当前节点的数据大
"""


class Tree:
    def __init__(self):
        self.root = None

    def insert(self, data):

        if self.root is None:
            self.root = Node(data)
            return

        current_node = self.root

        while current_node is not Node:

            if current_node.data == data:   # 这个数据已经在里面则跳出
                return

            elif data > current_node.data:    # 当前这个节点的值小于需要插入的值
                if current_node.right is None:      # 如果右节点为空插入这个节点数据
                    current_node.right = Node(data)
                else:                               # 不为空的时候需要继续比较下一级
                    current_node = current_node.right
            else:   # 当前节点的数据大于需要插入的数据
                if current_node.left is None:
                    current_node.left = Node(data)
                else:
                    current_node = current_node.left

    def print_tree(self, list_type=0):    # 遍历输出这颗树
        self.print_node(self.root, list_type)

    def print_node(self, node, list_type):

        if list_type == 0:  # 中遍历
            if node.left is not None:
                self.print_node(node.left, list_type)
            print(node.data)

            if node.right is not None:
                self.print_node(node.right, list_type)
        elif list_type == 1:    # 前序遍历
            print(node.data)
            if node.left is not None:
                self.print_node(node.left, list_type)
            if node.right is not None:
                self.print_node(node.right, list_type)
        elif list_type == 2:    # 后序遍历
            if node.left is not None:
                self.print_node(node.left, list_type)
            if node.right is not None:
                self.print_node(node.right, list_type)
            print(node.data)


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def get_data():
    return [8, 2, 21, 100, 58, 22, 75, 67, 61]


def main():
    n = int(input())
    data = [0] * n
    # data = get_data()
    for i in range(n):
        data[i] = int(input())

    tree = Tree()
    for i in data:
        tree.insert(i)

    tree.print_tree(2)
    return


if __name__ == '__main__':
    main()