解析数组存储二叉树2(优化版)

# 这样实现逻辑上比较好理解一点，但是确实浪费了一些存储空间


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

    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)

    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


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


tree = Tree()


def set_tree(data, start, end, node=None):

        # 操作获取到中间索引
        if (start + end) % 2 == 1:
            mid = (start + end) // 2 + 1
        else:
            mid = (start + end) // 2

        new_node = Node(data[mid])

        if tree.root is None:
            tree.root = new_node
        else:
            if data[mid] > node.data:
                node.right = new_node
            elif data[mid] < node.data:
                node.left = new_node

        left_end = mid - 1

        # 递归处理左子树
        if left_end >= start:
            set_tree(data, start, left_end, new_node)

        right_start = mid + 1
        # 递归处理右子树
        if right_start <= end:
            set_tree(data, right_start, end, new_node)


def get_data():
    n = int(input())
    return n, [int(input()) for i in range(n)]


def main():
    n, data = get_data()
    set_tree(data, 0, n-1)
    # print('根节点', tree.root.data)
    tree.print_tree(2)


if __name__ == '__main__':
    main()