0

那么我该如何解决这个问题呢？我需要一个程序，它从标准输入中读取一个正整数 n 并向标准输出写入顶点集合 {1,2,3....n} 上所有不同的有根、有序、标记树的表示。

对于输出，我需要使用L(t)树的以下线性文本表示t：

 If t is empty then L(t) = ().
 If t has root n and children, in sibling order, C = (c1; c2; : : : ; ck), then
 L(t) = (n, (L(c1), L(c2), : : :, L(ck)))
 where, L(ci) denotes the linear textual representation of the subtree rooted at
  child ci. There is a single space after each comma in the representation.

输出应在每一行包含一棵树的表示，并应按字典顺序对被视为字符串的线性表示进行排序。输出不应包含其他任何内容（例如虚假的换行符、提示或信息性消息）。n = 1 的样本输入和输出；2；出现在下方。

enter code here

Input: 1
Output:
(1, ())
Input: 2
Output:
(1, ((2, ()))) 
(2, ((1, ())))

enter code here

任何帮助将不胜感激。我只需要被引导到一个方向。现在，我完全被难住了:(

4

1 回答 1

0

您可以递归地生成树。从根开始。根可以有 0, 1, 2 ... (m - 1) 个子节点，其中 m 是您要放置的顶点数。首先在根下放置 (m - 1) 个顶点，然后一直向下到 0。您将递归地“放置”这些顶点，因此将顶点作为子节点放置在根下意味着再次调用相同的方法，但是这次孩子的最大数量会少一点。

您将获得递归的两个停止条件：

  • 您已经放置了所有 N 个顶点。您需要使用尚未定义的 L(t) 函数输出当前树，然后回溯以尝试不同的树。
  • 该算法将所有叶顶点的度数设为 0，而您尚未放置 n 个顶点。不要输出这棵树，因为它是无效的，而是回溯。

该算法在尝试给根节点 0 个子节点后完成。

至于输出L(t)函数，做深度优先树遍历似乎就足够了。递归是最容易编程的（因为这似乎是某种实际任务，这可能是他们希望你做的）。如果您需要速度，请在 Wikipedia 上查找非递归深度优先树遍历算法。

于 2013-09-28T22:37:16.773 回答