Python：二进制搜索T的数组实现

Question

我见过许多类型的二进制搜索树的链表实现，我想知道如何在数组中实现。这可能吗？如果是的话会是什么样子？ 非常感谢你！在

这是一个队列的数组实现！在

class Queue:

    MAX = 6

    def __init__(self):
        self.queue = [None for x in range(self.MAX)]
        self.front = 0
        self.rear = 0

    def isEmpty(self):
        return self.front == self.rear

    def size(self):
        if self.isEmpty():
            return 0
        elif self.front < self.rear:
            return self.rear - self.front
        else:
            return self.rear + self.MAX - self.front

    def isFull(self):
        return self.size() == self.MAX - 1

    def insert(self, data):
        if self.isFull():
            print("Cannot insert to full queue")
        else:
            self.queue[self.rear] = data
            self.rear = (self.rear + 1) % self.MAX
            return data


    def delete(self):
        if self.isEmpty():
            print("Cannot delete from empty queue")
        else:
            data = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.MAX
            return data

    def peek(self):
        if self.isEmpty():
            return None
        else:
            return self.queue[self.front]

    def display(self):
        if self.isEmpty():
            print("Empty Queue")
        elif self.front < self.rear:
            for i in range(self.front, self.rear):
                print(self.queue[i], end = ' ')
        else:
            for i in range(self.front, self.MAX):
                print(self.queue[i], end = ' ')
            for j in range(self.rear):
                print(self.queue[j], end = ' ')

Answer 1

我写过BSTs，但不知道如何使用“array”或“linked list”。以下是我和其他人通常会做的事情：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

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

    def add_node(self, val):
        # traversing the tree by comparing val with existing node value
        ...

    def remove_node(self, val):
        # whatever...

您将TreeNode存储在Tree中。在

Answer 2

你的问题有点混乱。队列是一种抽象数据类型，可以用多种方式实现。在数组或列表数据结构中实现它是一个标准的实现，正如您所看到的那样简单明了。在

二进制搜索树已经是一个实现——通常是一个抽象数据类型的实现，比如有序映射容器抽象数据类型。它取决于（有效地）创建和删除带有指向其他节点的链接的节点的能力。您通常需要用语言中实现这种创建和删除的原语来编写这个实现。将自己限制为数组类型会排除这些原语。在

然而，大多数语言在一个更原始的层上实现这些原语，即计算机处理地址空间（内存）。因此，可以假设数组类似于内存，并在该数组上实现自己的分配和释放机制。看看典型的内存分配算法，看看我在说什么。在

当然，这在实践中并不是一个好主意，但也许你这样做是作为一种学习经验。这当然需要一些学习！在

还有一个提示。您可能在考虑堆（在Pythonheapq模块中实现）。堆不是二叉搜索树，但它有一些相似之处，值得学习。在