data-structures - 给定一棵二叉搜索树，打印形成相同 BST 的所有输入组合

Question

例如，

输入的二叉树是

     2 
3         1 

我们需要打印相同二叉树结构的所有可能组合(不需要树平衡)

231、213

注意:123 不是有效输出，因为它会改变树结构。

如果模式较长，它会变得复杂。

另一个例子

         5 
      3     7
   2    4  6   8

在这种情况下

5 3 7 2 4 6 8

5 3 2 4 7 6 8

5 7 3 2 4 6 8

......................

我想知道是否有任何算法可以找到给出相同二叉树的模式。

Answer 1

这是一个在 Python 中使用回溯的简单算法。它假设一个带有 insert 操作的二叉搜索树的实现。每个节点在 node.value 处都有一个值，并且可能在 node.left 和 node.right 处有子节点。

def get_children(node):
    children = []
    if node.left is not None:
        children.append(node.left)
    if node.right is not None:
        children.append(node.right)
    return children

def print_permutations(possibilities, string):
    if len(possibilities) == 0:
        print(string)
        return

    for i in range(len(possibilities)):
        node = possibilities[i]
        del possibilities[i]
        new_possibilities = get_children(node) + possibilities
        print_permutations(new_possibilities, string + " " + str(node.value))
        possibilities.insert(i, node)

这个想法是，每次您从下一个数字的可能候选列表中选择一个节点时，您都​​会将该节点的子节点添加到您的可能候选列表中。一旦没有更多候选者，您就得出了一种可能的排序。

你可以这样调用它:

b = BinarySearchTree()
b.insert(5)
b.insert(3)
b.insert(7)
b.insert(2)
b.insert(4)
b.insert(6)
b.insert(8)

print_permutations(get_children(b.root), str(b.root.value))

它会输出:

5 3 2 4 7 6 8
5 3 2 4 7 8 6
5 3 2 7 6 8 4
5 3 2 7 6 4 8
5 3 2 7 8 6 4
...