Skip to main content
 首页 » 编程设计

python之数组到二叉搜索树

2025年05月04日13me-sa

我需要在 python 中创建一个从数组创建 BST 的函数。数组已经排序。

例子是:

function array_to_binary_search_tree(array, start, end) 
    if start > end 
        Return an empty value 
    mid := int((start + end) / 2) 
    tree := BinaryTree() 
    tree.node := array[mid] 
    tree.left := array_to_binary_search_tree(array, start, mid - 1) 
    tree.right := array_to_binary_search_tree(array, mid + 1, end) 
    Return 'tree' 

我有这个:

class BST: 
 
def __init__(self,tree,info): 
    self.right = None 
    self.left = None 
    self.info = info 
 
    def arrayToBST(seq): 
    if (seq == []): 
        return None 
    mid = ((len(seq)) // 2) 
    tree = BST(seq[mid]) 
    tree.left = arrayToBST(seq[0:mid]) 
    tree.right = arrayToBST(seq[mid+1:]) 
 
    return tree 
 
if __name__ == "__main__": 
    seq = [1,2,3,4,5,6,7,8,9] 
    arrayToBST(seq) 

结果是:

NameError: name 'arrayToBST' is not defined

我没有看到错误。请帮忙,谢谢!

请您参考如下方法:

在递归调用中,您正在调用实例的 arrayToBST 方法。因此,您需要调用 self.arrayToBST 而不仅仅是 arryToBST。 self 的全部意义在于让您访问实例上的属性。

您还应该创建一个实例并在您的主要部分调用该实例的 arrayToBST 方法。