排序的二进制树

Question

这是我用于BT的数组：

bt_array = [10, 3, 15, 1, None, 9]

这是我当前使用的代码。

def sorted_array(self): # NEEDS FIX
    # TODO: should return a sorted array
    elements=[]
    if self.left:
        elements += self.left.sorted_array()

    elements.append(self.internal_array)

    if self.right:
        elements += self.right.sorted_array()

    return elements

它返回了这一点：

sorted array [1, 3, None, 10, 9, 15]

但是我想按这样的smth来获取它：

 sorted array [None, 1, 3, 9, 10, 15]

或者没有一个可以留在这里的地方，但是9应该在10之前。

Answer 1

输入[10，3，15，1，none，9]描述了此树：

       10
      /  \
     3    15
    /    /
   1    9

这不是有效的二进制 search 树。值9应该是3的正确孩子。由于输入是错误的，因此无法信任输出。如果预期这样的输入，则应验证树是有效的bst 。

此外，这种输入格式通常由代码挑战站点（例如LEET代码）使用，而无值仅用作用级别式遍历明确描述树的存根。这些无值不应该包含在输出中。

如果您的代码在none值中产生列表，则表示您创建了具有属性internal_array的节点实例是none。这样的节点不应存在于树上。这种属性被称为这种方式也令人困惑，因为它肯定应该不是将数组作为值，而是一个简单的数字。

这是您可以使用的一些代码：

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

    @classmethod
    def from_level_order(Node, values):
        dummy = Node()
        queue = [dummy]
        isright = True
        for value in values:
            node = None if value is None else Node(value)
            if isright:
                queue.pop(0).right = node
            else:
                queue[0].left = node
            if node:
                queue.append(node)
            isright = not isright
        return dummy.right                

    def is_bst(self, lower = float('-inf'), upper = float('inf')):
        return (lower <= self.data <= upper
                and (not self.right or self.right.is_bst(self.data, upper))
                and (not self.left or self.left.is_bst(lower, self.data))
        )
    
    def __iter__(self):
        if self.left:
            yield from self.left
        yield self.data
        if self.right:
            yield from self.right

现在，对于您提供的示例输入，我们可以说它不是具有以下代码的有效BST：

tree = Node.from_level_order([10, 3, 15, 1, None, 9])
print(tree.is_bst())  # False

如果我们纠正输入（更改9到11），我们可以使用上述<代码> __ iter __ 方法（类似于您的功能）以获取排序列表：

tree = Node.from_level_order([10, 3, 15, 1, None, 11])
print(tree.is_bst())  # True
print(list(tree))  # [1, 3, 10, 11, 15]