2
3 1
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
...............
我想知道是否有任何算法可以找到给出相同二叉树的模式。
这是一个在Python中使用回溯(backtracking)的简单算法。它假设实现了一个具有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
...
2
1 3
2,1,3和2,3,1。规则是：根节点，然后是任意顺序的子节点。 5
3 7
2 4 6 8
一般有两种构建树的方法：广度优先和深度优先。使用广度优先，您会反复应用“先根节点，然后任意顺序遍历子节点”的规则。因此：
5,3,7,2,4,6,8
5,3,7,2,4,8,6
5,3,7,2,6,4,8
...
5,7,3,8,6,4,2
nodes_array = create an array of nodes that can be selected
output_array = array of selected nodes
add root to nodes_array
while nodes_array is not empty
temp = randomly select node from nodes_array, and remove it
if temp.left != null
add temp.left to nodes_array
if temp.right != null
add temp.right to nodes_array
append temp to output_array
end while
这应该总是生成一个有效的输入，因为除非其父节点已被选择，否则永远不会将子节点添加到输出数组中。
因此，生成所有有效组合的问题就变成了更改随机选择步骤，使得在每个级别它生成 nodes_array 的所有可能排列。生成排列是一个解决的问题。然而，递归应用这一点需要一些思考。
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
def printNodes(root):
if root == None:
return False
else:
print(root.data)
printNodes(root.left)
printNodes(root.right)
输出：
printNodes(root)
20
8
4
12
10
14
22
@deleterOfWorlds的答案可以，但他使用了一个在插入和删除时需要线性时间的列表。以下是我的Python解决方案，附有大量解释。
我们通过从左到右选择每个位置可能的选项中的一个节点来构建每个数组。我们将节点值添加到路径中，将节点的子节点（如果有）添加到可能性列表中，然后进一步递归。当没有更多选择时，我们有一个候选数组。为了生成其余的数组，我们回溯直到我们可以做出不同的选择，并再次递归。
关键是使用适合持有可能性的数据结构。列表可以，但在回溯时必须将节点放回到先前的位置（顺序很重要，因为我们已经添加了节点的子节点，必须在节点之后访问它们）。从列表中插入和删除需要线性时间。集合不起作用，因为它不维护顺序。字典最好，因为Python字典记住了插入顺序，而且所有操作均在常数时间内运行。
def bst_seq(root: TreeNode) -> list[list[int]]:
def _loop(choices: MutableMapping[TreeNode, bool], path: list[int], result: list[list[int]]) -> None:
if not choices:
result.append([*path])
else:
# Take a snapshot of the keys to avoid concurrent modification exception
for choice in list(choices.keys()):
del choices[choice]
children = list(filter(None, [choice.left, choice.right]))
for child in children:
choices[child] = False
path.append(choice.val)
_loop(choices, path, result)
path.pop()
choices[choice] = False
for child in children:
del choices[child]
result = []
_loop({root: False}, [], result)
return result
1 2 3 4 5是你例子中树的有效模式吗？如果不是，为什么不是？ - Bernhard Barker123不合法是因为它会改变树的结构，但是，由于你没有给出从模式生成树的规则，所以你画的树可能是123的有效树。我猜测你认为该模式是树的层序遍历（参见 维基百科），但你绝对需要明确说明这一点。 - Bernhard Barker