为mergesort算法创建决策树

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 }合并时，我只有一个决定，检查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个排列，相当大的树。