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

我正在尝试制作一个算法，该算法创建一个完整的二叉搜索树，给出一个值列表。完整的是，除了最后一层以外，所有层次都是完整的，它需要尽可能将所有元素向左移动。从列表中创建一个完整的二叉搜索树

我已经实现的东西（在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是这样的：

你有如何的任何建议修改我的方法来完成这个？

来源

2013-10-10 computmaxer

你必须添加你的平衡旋转：P –

使用'int（len（arr）/ 2）'找到中间节点是不正确的。例如，在一个有11个节点的树中，左子树有7个节点，右子树有3个节点。您目前的方法会在左侧放五个，右侧放五个。 – Kevin

你应该阅读关于AVL树 – Rerito

完整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所以根是从左侧（情况1）或右（情况2）计数2**d个节点。您只需扣除1，因为索引编制起始于0。

来源

2014-11-12 21:01:55 Hannes

-1

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

来源

2013-10-10 19:32:45 tskuzzy

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

回答

相关问题