python顺序存储二叉树

Question

如何用代码实现二叉树顺序存储，实现查找，求高度先，中，后，层次遍历

Answer 1

下面是二叉树顺序存储实现，包括查找，求高度，先序遍历，中序遍历，后序遍历和层次遍历的详细代码

class BinaryTree:
    def __init__(self, size):
        self.data = [None] * size
        self.size = size

    def get_parent_index(self, index):
        return (index - 1) // 2 if index > 0 else -1

    def get_left_child_index(self, index):
        left_child_index = index * 2 + 1
        return left_child_index if left_child_index < self.size else -1

    def get_right_child_index(self, index):
        right_child_index = index * 2 + 2
        return right_child_index if right_child_index < self.size else -1

    def get_height(self):
        height = 0
        level_size = 1
        while level_size <= self.size:
            height += 1
            level_size *= 2
        return height - 1

    def insert(self, value):
        if None not in self.data:
            return False

        self.data[self.data.index(None)] = value
        return True

    def find(self, value):
        for i in range(self.size):
            if self.data[i] == value:
                return i
        return -1

    def pre_order_traversal(self, index):
        if index == -1:
            return

        print(self.data[index], end=" ")
        self.pre_order_traversal(self.get_left_child_index(index))
        self.pre_order_traversal(self.get_right_child_index(index))

    def in_order_traversal(self, index):
        if index == -1:
            return

        self.in_order_traversal(self.get_left_child_index(index))
        print(self.data[index], end=" ")
        self.in_order_traversal(self.get_right_child_index(index))

    def post_order_traversal(self, index):
        if index == -1:
            return

        self.post_order_traversal(self.get_left_child_index(index))
        self.post_order_traversal(self.get_right_child_index(index))
        print(self.data[index], end=" ")

    def level_order_traversal(self):
        for i in range(self.size):
            if self.data[i] is not None:
                print(self.data[i], end=" ")

    def __str__(self):
        return str(self.data)

tree = BinaryTree(7)
tree.insert(2)
tree.insert(3)
tree.insert(5)
tree.insert(7)
tree.insert(1)
tree.insert(6)

print(tree.pre_order_traversal(0)) # 2 1 3 5 7 6
print(tree.in_order_traversal(0)) # 1 2 3 5 6 7
print(tree.post_order_traversal(0)) # 1 6 7 5 3 2
print(tree.level_order_traversal()) # 2 1 3 5 7 6
print(tree.get_height()) # 2

以上代码实现的是完全二叉树的顺序存储，并不适用于普通的二叉树，但是一般不会让你写不标准的