没有类，但作为列表列表的二叉搜索树

Question

如何实现没有 class 结构但作为列表的列表的 BST？找不到这样的实现，自己试了一下：

numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
tree = []

for num in numbers:
    tree.append( [num, 0, 0] )

for num in numbers[1:]:
    for l in tree:
        if num != l[0]:
            if num > l[0]:
                if l[2] == 0:
                    l[2] = numbers.index(num)
                    break
            else:
                if l[1] == 0:
                    l[1] = numbers.index(num)
                    break

树的每个元素都有一个列表。

tree[i][0] 将是节点的值。
tree[i][1], tree[i][2] 将是 i 处节点的左右节点的索引。

遗憾的是这不起作用（没有错误）。对于上面的例子，它看起来像这样（根在左边）：

# [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
#
#          15
#         /  \
#        /    8
#      13
#     /  \
#    /    4
#   /
#  7
#   \       10
#    \     /  \
#     \   /    3
#      \ /
#       2
#        \   1
#         \ /
#          0

如您所见，10 变成了 2 的左 child，而它应该是 13 的右 child。

Answer 1

如果我理解正确的话，你希望树是一个三元组列表，其中每个三元组代表树的一个节点，由 [value, left, right] 组成，其中 left 和 right 是整个列表中的索引，引用相关的子节点，否则为 0.

你的代码中的问题是你并没有真正沿着那些父子关系遍历树。相反，您只需使用 for l in tree 从左到右迭代它。相反，您应该 l = tree[l[1]] 或 l = tree[l[2]] 从父节点转到子节点。

其次，永远不应该发生 num == l[0]（根本身除外，您的代码无论如何都会跳过它），因为这意味着该数字已经从父节点链接并且您有一个重复的.如果发生这种情况，则应忽略重复项，并退出循环。

所以这是对主循环的更正：

for i, num in enumerate(numbers):
    l = tree[0]
    while num != l[0]:
        if num > l[0]:
            if l[2] == 0:
                l[2] = i
                break
            l = tree[l[2]]  # walk down to right child
        else:
            if l[1] == 0:
                l[1] = i
                break
            l = tree[l[1]]  # walk down to left child

请注意，我在循环中使用了 enumerate，以避免您必须调用 index。

我还建议至少创建函数，并将在树中查找一个值的逻辑与插入一个值的逻辑分开.此外，命名可以改进：

VALUE = 0
LEFT = 1
RIGHT = 2

def find(tree, num):
    if not tree:
        return
    node = tree[0]
    while num != node[VALUE]:
        i = node[RIGHT if num > node[VALUE] else LEFT]  # index of child
        if i == 0:  # no child in that direction
            return node
        node = tree[i]
    return node

def insert(tree, num):
    if tree:
        node = find(tree, num)
        if num == node[VALUE]:
            return
        node[RIGHT if num > node[VALUE] else LEFT] = len(tree)
    tree.append([num, 0, 0])


numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
tree = []
for num in numbers:
    insert(tree, num)
print(tree)

没有类，但作为列表列表的二叉搜索树

Binary Search tree without classes, but as list of lists

python

python-3.x

list

binary-tree

binary-search-tree

没有 类，但作为列表列表的二叉搜索树

Binary Search tree without classes, but as list of lists

python

python-3.x

list

binary-tree

binary-search-tree

没有类，但作为列表列表的二叉搜索树