1

这是作业，我想起来有困难。请给我一些关于递归和DP解决方案的想法。非常感谢

生成并打印所有结构上不同的完整二叉树，其中 n 个叶子以点括号的形式出现，“完整”表示所有内部（非叶子）节点正好有两个子节点。

例如，有 5 棵不同的满二叉树，每棵树有 4 个叶子。

4

4 回答 4

3

在 Python 中，你可以这样做

def gendistinct(n):
    leafnode = '(.)'
    dp = []
    newset = set()
    newset.add(leafnode)
    dp.append(newset)
    for i in range(1,n):
        newset = set()
        for j in range(i):
            for leftchild in dp[j]:
                for rightchild in dp[i-j-1]:
                    newset.add('(' + '.' + leftchild + rightchild + ')')
        dp.append(newset)
    return dp[-1]

alltrees = gendistinct(4)
for tree in alltrees:
    print tree
于 2012-09-06T06:52:51.603 回答
2

另一个具有不同策略的 Python 示例。

这是递归的并使用生成器。它比这里的其他实现要慢，但应该使用更少的内存，因为一次只能在内存中存在一个列表。

#!/usr/bin/env python

import itertools

def all_possible_trees(n):
    if n == 1:
        yield 'l'
    for split in range(1, n):
        gen_left = all_possible_trees(split)
        gen_right = all_possible_trees(n-split)
        for left, right in itertools.product(gen_left, gen_right):
            yield [left, right]

if __name__ == '__main__':
    import sys
    n = int(sys.argv[1])
    for thing in all_possible_trees(n):
        print(thing)
于 2017-01-12T15:46:48.243 回答
1

我没有看到一个明显的递归方法，但毫无疑问有一个。

相反，我会尝试动态编程方法。

请注意，根据您对完整树的定义，具有 n 个叶子的树具有 n-1 个内部节点。另请注意，可以通过在根部将两棵树连接在一起，左侧为 1 到 n-1 片叶子，右侧为 n-1 到 1 片叶子，从而从较小的树中生成树。

另请注意，各种大小的“树”可以存储为点括号字符串。要从这些构建新树，请连接（左，右）。

因此，从具有 1 个叶子的单棵树（即单个节点）开始。构建大小增加到 n 的树的列表。要构建 k-叶子树的列表，对于每个 j = 1 到 k-1，对于每个 j 个叶子的树，对于每个 kj 个叶子的树，连接以构建树（具有 k 个叶子）并添加到列表中。

在构建 n 叶树时，您可以将它们打印出来而不是存储它们。

有 5*1 + 2*1 + 1*2 + 1*5 = 14 棵树，有 5 片叶子。

有 14*1 + 5*1 + 2*2 + 1*5 + 1*14 = 42 棵树，有 6 片叶子。

于 2012-09-06T05:20:39.883 回答
0

U can use recursion, on i-th step u consider i-th level of tree and u chose which nodes will be present on this level according to constraints: - there is parent on previous level - no single children present (by your definition of "full" tree)

recursion ends when u have exactly N nodes.

于 2012-09-06T05:22:41.380 回答