生成深度为 N 的所有可能的树? [英] Generating all possible trees of depth N?
问题描述
我有几种不同类型的树节点,每个节点可能有 0 到 5 个子节点.我正在尝试找出一种算法来生成所有可能的深度 <= N 树.这里有什么帮助吗?鉴于我对节点所做的每次更改都可能暴露新的子树(或删除旧的子树),因此我无法弄清楚如何递归地遍历树.
这是我编写的 Python 程序,我认为它可以满足您的要求.给定一个起始节点,它将返回所有可能的树.本质上,它归结为一个位操作技巧:如果一个节点有 5 个子节点,那么有 25 = 32 个不同的可能子树,因为每个子节点可以独立存在或不存在于子树中.
代码:
#!/usr/bin/env pythondef all_combos(选择):"""给定一个项目列表 (a,b,c,...),生成所有可能的组合其中一项取自 a,一项取自 b,一项取自 c,依此类推.例如, all_combos([[1, 2], ["a", "b", "c"]]) 产生:[1, 一个"][1, "b"][1, "c"][2, 一个"][2, "b"][2, "c"]"""如果不是选择:屈服 []返回对于 selection[0] 中的 left_choice:对于 all_combos(choices[1:]) 中的 right_choices:产量 [left_choice] + right_choices类节点:def __init__(self, value, children=[]):self.value = 价值self.children = 孩子def all_subtrees(self, max_depth):产量节点(self.value)如果 max_depth >0:# 对于每个孩子,获取其所有可能的子树.child_subtrees = [list(self.children[i].all_subtrees(max_depth - 1)) for i in range(len(self.children))]# 现在让 n 个孩子遍历 2^n 种可能性,其中# 每个孩子的子树独立存在或不存在.这# 如果bits"中的第 i 位为 1,则存在第 i 个孩子.对于 xrange(1, 2 ** len(self.children)) 中的位:对于 all_combos([child_subtrees[i] for i in range(len(self.children)) 中的组合,如果 bits & (1 << i) != 0]):产量节点(self.value,组合)def __str__(self):"""显示节点的值,然后在括号中显示其子节点(如果有)."""如果 self.children:返回 "%s %s" % (self.value, self.children)别的:返回 str(self.value)def __repr__(self):返回 str(self)树 = 节点(1,[节点(2),节点(3,[节点(4),节点(5),节点(6)])])对于 tree.all_subtrees(2) 中的子树:打印子树
这是测试树的图形表示:
<前>1/2 3/|4 5 6这是运行程序的输出:
<前>11 [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++ 或其他任何东西中会更冗长.
I have several different types of tree nodes, each of which may have anywhere from 0 to 5 children. I'm trying to figure out an algorithm to generate all possible trees of depth <= N. Any help here? I'm having trouble figuring out how to recursively walk the tree given that each change I make to a node may expose new subtrees (or remove old ones).
Here's a Python program I wrote up that I think does what you're asking. It'll return all of the possible trees given a starting node. Essentially, it boils down to a trick with bit manipulation: if a node has 5 children, then there are 25 = 32 different possible subtrees as each child can independently be present or not present in a subtree.
Code:
#!/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
Here's a graphical representation of the test tree:
1 / 2 3 /| 4 5 6
And here's the output from running the program:
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]]
If you'd like I could translate this into a different language. You didn't specify so I used Python; the code would be a bit more verbose in Java or C++ or whatever since I took advantage of Python's list comprehensions in a big way.
这篇关于生成深度为 N 的所有可能的树?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!