python使用现有函数创建二叉搜索树

Question

我正在练习用Python创建一个平衡的二叉搜索树。我已经有了以下这些，关于如何创建一个balance_bst函数的任何想法，该函数传递了一个按递增顺序排序的唯一值列表。它返回对平衡良好的二叉搜索树的根的引用：

class LN:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front

def str_ll(ll):
    answer = ''
    while ll != None:
        answer += str(ll.value)+'->'
        ll = ll.next
    return answer + 'None'



# Tree Node class and helper functions (to set up problem)

class TN:
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left  = left
        self.right = right

def height(atree):
    if atree == None:
        return -1
    else:
        return 1+ max(height(atree.left),height(atree.right))

def size(t):
    if t == None:
        return 0
    else:
        return 1 + size(t.left) + size(t.right)

def is_balanced(t):
    if t == None:
        return True
    else:
        return abs(size(t.left)-size(t.right)) <= 1 and is_balanced(t.left) and is_balanced(t.right)

def str_tree(atree,indent_char ='.',indent_delta=2):
    def str_tree_1(indent,atree):
        if atree == None:
            return ''
        else:
            answer = ''
            answer += str_tree_1(indent+indent_delta,atree.right)
            answer += indent*indent_char+str(atree.value)+'\n'
            answer += str_tree_1(indent+indent_delta,atree.left)
            return answer
    return str_tree_1(0,atree) 

如何编写balance_bst？

def balance_bst(l):

def build_balanced_bst(l):
    if l == None:
        return None
    else:
        middle = len(l) // 2
        return TN(l[middle],
        build_balanced_bst(l[:middle]),
        build_balanced_bst(l[middle + 1:]))

IndexError: list index out of range

我怎么修好它？

Answer 1

我不打算为你写它，因为这不是为什么，但大致的想法是这样的。由于列表已经排序，根应该是列表中间的元素。它的左子树将是由列表中根左边的元素组成的平衡树的根，右子树将是其余的子树。