python - 从列表中创建一个完整的二叉搜索树

Question

我正在尝试制作一种算法，该算法可以在给定值列表的情况下创建完整的二叉搜索树。完成，因为除了最后一个级别，所有级别都已满，这需要将所有元素尽可能地向左移动。

我已经实现了一些（在 Python 中）将创建一个平衡的 BST，如下所示：

# TreeNode constructor takes (data, left, right, parent)
def make_tree(arr, parent):
    if not arr:
        return None

    length = len(arr)
    if length == 1:
        return TreeNode(arr[0], None, None, parent)
    else:
        mid = int(len(arr)/2)
        mid_node = TreeNode(arr[mid], None, None, parent)
        mid_node.left = make_tree(arr[0:mid], mid_node)
        mid_node.right = make_tree(arr[mid+1:length], mid_node)
        return mid_node

它的工作原理是通过中点递归地拆分列表，并使中点成为父节点。

但是，这不会创建完整的BST。给定列表 [2,4,7,8,10]，它将创建：

但是一个完整的 BST 应该是这样的：

您对如何修改我的方法来实现这一点有什么建议吗？

score 5 · Accepted Answer

完整 BST 的构建类似于平衡 BST。你只需要找到正确的中间。我使用了以下功能：

def perfect_tree_partition(n):
    """find the point to partition n keys for a perfect binary tree"""
    x = 1

    # find a power of 2 <= n//2
    # while x <= n//2:  # this loop could probably be written more elegantly :)
    #     x *= 2
    x = 1 << (n.bit_length() - 1)   # indeed you can

    if x//2 - 1 <= (n-x):
        return x - 1      # case 1
    else:
        return n - x//2   # case 2 == n - (x//2 - 1) - 1

有两种情况：要么

情况1：根的左子树是完美的，右子树的节点较少或
情况2：根的左子树节点较多，右子树是完美的。

在这两种情况下，完美子树中的节点数都是一些2**d - 1，因此根是2**d从左侧（情况 1）或右侧（情况 2）计数的第一个节点。你只需要减去1，因为索引从0.

score -1 · Accepted Answer

如果这只是一次性操作，可以先对列表进行排序，然后再构造 BST。这使问题变得微不足道。

python - 从列表中创建一个完整的二叉搜索树

2 回答 2

Related

Reference