用于创建二进制搜索树的递归函数。

Question

我现在正在读这本书 破解密码面试，试图在编码方面获得一个后裔水平（虽然我离这个水平还很远）。

问题是这样的。给定一个具有唯一整数元素的排序（递增顺序）数组，写出analgorithm来创建一个高度最小的二进制搜索树。

这是我的尝试。

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

class binaryTree:
    def __init__(self,nodes,root):
        self.nodes = nodes
        self.root = root

def minimalTree(sortedArray):
    if not sortedArray:
        return None

    else:
        lengthArray = len(sortedArray)
        middle = lengthArray//2
        print("middle = ", middle)
        root = Node(sortedArray[middle])
        leftArray = array.array('i',[])
        rightArray = array.array('i',[])
        if middle == 0:
            return root
        if middle > 0:
            leftArray = sortedArray[0:middle]
            root.left = Node(leftArray[len(leftArray)//2])

        if middle + 1 < lengthArray: 
            rightArray = sortedArray[middle+1:lengthArray]
            root.right = Node(leftArray[len(rightArray)//2])

        return minimalTree(leftArray),minimalTree(rightArray)

正如你所看到的，我并没有真正使用二进制树类，但我不确定它是否有用，因为树可以由它的根给出。

不过我还是在努力学习递归算法，我不明白为什么这个算法不返回任何东西。

请注意，我的问题不是关于我提出的算法的正确性或效率（虽然也欢迎大家对此提出意见）。

编辑一下。 我已经编辑了代码，试图按照建议加入基本情况。

Answer 1

minimalTree函数需要更正

需要一个基本案例，当数组为空时返回。

if lengthArray == 0:
  return None

你需要递归地分配左和右（独立于中间）。

# Array split a middle
leftArray = sortedArray[0:middle]
rightArray = sortedArray[middle+1:lengthArray]

# Left side recursion
root.left = minimalTree(leftArray)

# Right side recursion
root.right = minimalTree(rightArray)

你需要返回根

return root

经过上述重构后的minimalTree代码

def minimalTree(sortedArray):
    lengthArray = len(sortedArray)

    # Base case of recursion
    if lengthArray == 0:
      return None

    # Assign middle
    middle = lengthArray//2
    root = Node(sortedArray[middle])

    # Split Left & Right sides
    leftArray = sortedArray[0:middle]
    rightArray = sortedArray[middle+1:lengthArray]

    # Left & right recursions
    root.left = minimalTree(leftArray)
    root.right = minimalTree(rightArray)

    return root

显示树

def display(node): 
    if not node: 
        return

    print (node.value)
    display(node.left)
    display(node.right)

测试

tree = minimalTree([1, 2, 3, 4, 5])
display(tree)

产量

3
2
1
5
4