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]，它将创建这个:

      7

   /    \ 

  4     10

/       /

2      8

但是完整的 BST 应该是这样的:

      8

   /    \ 

  4     10

 /  \ 

2    7 

对于如何修改我的方法以实现此目的，您有什么建议吗？

Answer 1

完整 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 开始。