我有几种不同类型的树节点，每个节点可能有 0 到 5 个子节点。我正在尝试找出一种算法来生成所有可能的深度树<= N。这里有什么帮助吗？鉴于我对节点所做的每次更改都可能暴露新的子树（或删除旧的子树），我无法弄清楚如何递归地遍历树。
JoeF
问问题
2328 次
4 回答
4
这是我编写的一个 Python 程序，我认为它可以满足您的要求。给定一个起始节点，它将返回所有可能的树。本质上，它归结为一个位操作技巧：如果一个节点有 5 个子节点，则有 2 5 = 32 个不同的可能子树，因为每个子节点可以独立存在或不存在于子树中。
代码：
#!/usr/bin/env python
def all_combos(choices):
"""
Given a list of items (a,b,c,...), generates all possible combinations of
items where one item is taken from a, one from b, one from c, and so on.
For example, all_combos([[1, 2], ["a", "b", "c"]]) yields:
[1, "a"]
[1, "b"]
[1, "c"]
[2, "a"]
[2, "b"]
[2, "c"]
"""
if not choices:
yield []
return
for left_choice in choices[0]:
for right_choices in all_combos(choices[1:]):
yield [left_choice] + right_choices
class Node:
def __init__(self, value, children=[]):
self.value = value
self.children = children
def all_subtrees(self, max_depth):
yield Node(self.value)
if max_depth > 0:
# For each child, get all of its possible sub-trees.
child_subtrees = [list(self.children[i].all_subtrees(max_depth - 1)) for i in range(len(self.children))]
# Now for the n children iterate through the 2^n possibilities where
# each child's subtree is independently present or not present. The
# i-th child is present if the i-th bit in "bits" is a 1.
for bits in xrange(1, 2 ** len(self.children)):
for combos in all_combos([child_subtrees[i] for i in range(len(self.children)) if bits & (1 << i) != 0]):
yield Node(self.value, combos)
def __str__(self):
"""
Display the node's value, and then its children in brackets if it has any.
"""
if self.children:
return "%s %s" % (self.value, self.children)
else:
return str(self.value)
def __repr__(self):
return str(self)
tree = Node(1,
[
Node(2),
Node(3,
[
Node(4),
Node(5),
Node(6)
])
])
for subtree in tree.all_subtrees(2):
print subtree
这是测试树的图形表示：
1 / \ 2 3 /|\ 4 5 6
这是运行程序的输出：
1 1 [2] 1 [3] 1 [3 [4]] 1 [3 [5]] 1 [3 [4, 5]] 1 [3 [6]] 1 [3 [4, 6]] 1 [3 [5, 6]] 1 [3 [4, 5, 6]] 1 [2, 3] 1 [2, 3 [4]] 1 [2, 3 [5]] 1 [2, 3 [4, 5]] 1 [2, 3 [6]] 1 [2, 3 [4, 6]] 1 [2, 3 [5, 6]] 1 [2, 3 [4, 5, 6]]
如果你愿意，我可以把它翻译成另一种语言。您没有指定，所以我使用了 Python；由于我在很大程度上利用了 Python 的列表推导，因此在 Java 或 C++ 或其他任何代码中代码会更加冗长。
于 2009-07-21T19:51:16.497 回答
1
您可以创建一个包含 for 循环的函数，该循环将元素添加到多维数组并再次调用该函数，直到树完成。我无法提供示例，因为我不知道您喜欢哪种语言。
于 2009-07-21T16:08:20.830 回答
0
如果节点类型之间的唯一区别是子节点的数量，那么仅生成具有最多子节点类型的每个可能的树也将为具有相等或更少子节点的任何节点组合生成每个可能的树。
有点口无遮拦...
换句话说，如果最多有 5 个子节点，那么某些仅由 5 个子节点组成的可能树的节点将具有例如两个实际子节点和三个空指针的节点。这实际上与只有两个孩子的节点相同。
于 2009-07-22T02:58:45.273 回答