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

我不會爲你寫它，因爲這不是什麼關於，但這是一般的想法。由於列表已經排序，所以根應該是列表中間的元素。它的左邊的孩子將成爲平衡樹的根，該平衡樹由列表中根元素左邊的元素組成，右邊的子樹將成爲其餘元素。