如何仅用数组实现二叉搜索树（不使用链表）？本人已掌握链表实现方式

Hey there! Glad you've already nailed the linked-list approach to BSTs—now let's walk through how to build one using just an array. The key here is using index arithmetic to replicate the parent-child relationships that links handle automatically.

Core Idea: Index Mapping for Parent-Child Nodes #

In an array-based binary tree, we follow a standard indexing rule to locate a node's children and parent:

• For any node at index i:
  • Left child is at 2 * i + 1
  • Right child is at 2 * i + 2
  • Parent node is at (i - 1) // 2 (integer division)

Since BSTs aren't always complete binary trees, we'll use a placeholder (like None in Python) to mark empty positions in the array where no node exists.

Step-by-Step Implementation #

1. Inserting Nodes #

Insertion works just like in a linked-list BST—we compare values to traverse the tree—but we use the index rules to navigate the array instead of following pointers:

• Start at the root (index 0). If the array is empty, add the value here first.
• For each current node:
  • If the new value is smaller, move to the left child index. If that position is empty (or out of the array's bounds), place the value there. Otherwise, keep traversing left.
  • If the new value is larger, move to the right child index and do the same check.
• We'll need to dynamically expand the array if the target index is beyond the current length, filling the gaps with our empty placeholder.

Here's a concrete Python example:

class ArrayBST:
    def __init__(self):
        self.tree = []  # Uses None as empty node placeholder

    def insert(self, value):
        # Handle empty tree case
        if not self.tree:
            self.tree.append(value)
            return

        index = 0
        while True:
            current_val = self.tree[index]
            # Traverse left for smaller values
            if value < current_val:
                left_idx = 2 * index + 1
                # Expand array if needed
                if left_idx >= len(self.tree):
                    self.tree.extend([None] * (left_idx - len(self.tree) + 1))
                # Place value if left child is empty
                if self.tree[left_idx] is None:
                    self.tree[left_idx] = value
                    break
                else:
                    index = left_idx
            # Traverse right for larger/equal values
            else:
                right_idx = 2 * index + 2
                if right_idx >= len(self.tree):
                    self.tree.extend([None] * (right_idx - len(self.tree) + 1))
                if self.tree[right_idx] is None:
                    self.tree[right_idx] = value
                    break
                else:
                    index = right_idx

    def search(self, value):
        index = 0
        while index < len(self.tree):
            current_val = self.tree[index]
            if current_val is None:
                return False  # Hit an empty spot, value doesn't exist
            if current_val == value:
                return True
            elif value < current_val:
                index = 2 * index + 1
            else:
                index = 2 * index + 2
        return False

2. Traversing the Tree #

Traversals (in-order, pre-order, post-order) follow the same logic as linked-list BSTs—you just use the index rules to access children instead of pointers. For example, an in-order traversal (which gives sorted values for BSTs) would look like this:

def in_order_traversal(self, index=0, result=None):
    if result is None:
        result = []
    if index >= len(self.tree) or self.tree[index] is None:
        return result
    # Traverse left subtree
    self.in_order_traversal(2 * index + 1, result)
    # Visit current node
    result.append(self.tree[index])
    # Traverse right subtree
    self.in_order_traversal(2 * index + 2, result)
    return result

Key Considerations #

• Space Efficiency: If your BST becomes unbalanced (e.g., it degenerates into a linked list), the array will have a lot of empty placeholders, leading to wasted space. This is a tradeoff compared to linked-list BSTs, which only use space for existing nodes. For balanced BSTs (like AVL or Red-Black trees), though, array-based implementations are much more space-efficient.
• Dynamic vs Static Arrays: Static arrays require you to pre-allocate enough space for the maximum possible tree size. Dynamic arrays (like Python's list) handle expansion automatically, which is more convenient for most use cases.
• Deletion: Deletion works similarly to insertion but requires more care—you'll need to replace the deleted node with its in-order successor/predecessor and update the array accordingly, making sure to maintain the index mapping rules.

内容的提问来源于stack exchange，提问作者Susmoy Barman