如何不使用类结构、以嵌套列表形式实现二叉搜索树BST

问题原因 #

你的代码存在三个核心逻辑错误，导致生成的结构不符合BST规则：

• 插入路径错误：BST插入新节点必须从根节点（下标0）开始，逐层比较大小选择左/右子树路径，直到找到空的子节点位再插入。你原代码是遍历所有tree节点，碰到第一个符合数值大小关系且子位为空的节点就直接插入，完全没有走BST的层级查找路径，因此出现10错误挂载到2节点下的问题。
• 空节点标识不合理：你初始把左右子节点设为0，而0是根节点的有效下标，判断l[2]==0时无法区分是空节点还是指向根节点，应该用-1作为空节点的标识。
• 下标查询风险：numbers.index(num)在数组存在重复值时只会返回第一个匹配项的下标，直接使用遍历索引更安全。

正确实现代码 #

numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
# 每个节点结构：[存储值, 左子节点下标, 右子节点下标]，-1表示空节点
tree = []

# 初始化所有节点，左右子节点默认设为-1
for num in numbers:
    tree.append([num, -1, -1])

# 从第二个元素开始逐个插入BST
for idx in range(1, len(numbers)):
    current_num = numbers[idx]
    # 每次插入都从根节点（下标0）开始查找位置
    cur_pos = 0
    while True:
        node_val = tree[cur_pos][0]
        if current_num < node_val:
            # 小于当前节点走左子树
            if tree[cur_pos][1] == -1:
                tree[cur_pos][1] = idx
                break
            cur_pos = tree[cur_pos][1]
        else:
            # 大于等于当前节点走右子树，重复值处理逻辑可按需调整
            if tree[cur_pos][2] == -1:
                tree[cur_pos][2] = idx
                break
            cur_pos = tree[cur_pos][2]

结构验证 #

生成的tree完全符合BST规则：

• 根节点7的左子节点为下标1（值2）、右子节点为下标2（值13）
• 13的左子节点为下标4（值10）、右子节点为下标5（值15）
• 10的左子节点为空、右子节点为下标9（值8），和预期结构完全一致。

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