用n个叶子生成所有结构上不同的完整二叉树 [英] generate all structurally distinct full binary trees with n leaves

问题描述

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

This is a homework, I have difficulties in thinking of it. Please give me some ideas on recursions and DP solutions. Thanks a lot

生成并打印所有结构不同的完整二元
树，其中n片叶子用点括号括起来，
完整表示所有内部（非叶）节点有
个正好是两个孩子。

generate and print all structurally distinct full binary trees with n leaves in dotted parentheses form， "full" means all internal (non-leaf) nodes have exactly two children.

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

For example, there are 5 distinct full binary trees with 4 leaves each.

推荐答案

U可以使用递归，在第i步上，您考虑树的第i层，并且您选择了哪个节点是根据限制出现在该级别上：
-上一级有父级
-没有单子出现（根据您对完整树的定义）

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)

当您恰好有N个节点时，递归结束。

recursion ends when u have exactly N nodes.

这篇关于用n个叶子生成所有结构上不同的完整二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！