从列表中创建完整的二叉搜索树

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)计数的第th个节点.你只需要减去1因为索引开始于0.