algorithm - 为合并排序算法创建决策树

Question

在我的作业中，我需要为任意输入 S={a,b,c} 创建 n=3 的决策树。

这是我的递归调用树。 S={a,b,c} 变成 S={a} 和 S={b,c} 和 S={b,c} 变成 S={b} 和 S={c}。在基本情况下，我有 S={a}、S={b} 和 S={c}。

当我将 S={b} 与 S={c} 合并时，我只有 1 个决定，检查是否 b < c。如果为真，则 S={b,c}。否则，S={c,b}。

之前合并 b 和 c 返回的任何内容都与 S={a} 合并。

在 S={a} 和 S={b,c} 的合并中，我有几个决定。我首先检查是否 a < b。如果为真，并且由于 S={b,c} 已排序，则 S={a,b,c}。如果为假，我还有另一个决定要做。检查是否 a < c。如果为真，则 S={b,a,c}。否则，S={b,c,a}。

这让我陷入困境。如何将我的所有工作合并到一个决策树中？我可以毫无问题地为迭代算法创建决策树，但是由于该算法是递归的，所以我很困惑。

感谢任何帮助。谢谢。

Answer 1

您必须从递归的最深层次开始遵循补丁。在这种情况下，树的顶部是“if (b <= c)”。然后，如果为真，正如您已经提到的，它是“if (a <= b”) S={a,b,c} else “if (a <= c”) S = {b,a,c}” “else S = {b, c, a}”，则当“if (b <= c)”为假时，模式类似。

我不确定这有什么意义。在 n=4 的情况下，您有 24 种可能的排列，对于 n = 5，有 120 种排列，相当大的树。