1

可以使用两个函数对二叉树进行编码l，r 对于 a node n，l(n)给出 的左孩子n，r(n) 给出 的右孩子n。

树的分支是从根到叶子的路径，分支到特定叶子的长度是从根到该叶子的路径上的弧数。

让MinBranch(l,r,x)是一个简单的递归算法，用于获取由 l 和 r 函数编码的二叉树以及二叉树的根节点 x，并返回二叉树最短分支的长度。

给出这个算法的伪代码。

好的，所以基本上这就是我到目前为止想出的：

MinBranch(l, r, x)
{
    if x is None return 0

    left_one = MinBranch(l, r, l(x))

    right_one = MinBranch(l, r, r(x))

    return {min (left_one),(right_one)}
}

显然这不是很好或完美的。如果人们能帮助我完成这个完美的工作，我会很感激 - 任何帮助都将不胜感激。

4

5 回答 5

3

我怀疑有人会直接为你解决家庭作业。一条线索：随着树变大，返回值肯定会变高，对吧？但是，除了 0 之外，我在您的函数中看不到任何数字文字，也没有加法运算符。你将如何返回更大的数字？

关于同一问题的另一个角度：每当您编写递归函数时，它有助于枚举“我应该停止调用自己的所有条件是什么？在每种情况下我返回什么？”

于 2009-08-28T04:15:29.273 回答
2

你的方法是正确的，但你并不完全在那里；您的递归算法将始终返回 0。（尽管逻辑几乎是正确的......）

注意子分支的长度比分支的长度小一；所以left_one应该right_one是1 + MinBranch...。

使用一些样本树逐步完成算法将有助于发现像这样的错误...

于 2009-08-28T04:16:03.203 回答
1

看起来您几乎拥有它，但请考虑以下示例：

      4

   3     5

当您跟踪时MinBranch，您会在 MinBranch(l,r,4)通话中看到：

left_one = MinBranch(l, r, l(x))
         = MinBranch(l, r, l(4))
         = MinBranch(l, r, 3)
         = 0

这是有道理的，毕竟 3 是一个叶子节点，所以到最近的叶子节点的距离当然是 0。right_one 也是如此。

但是你会在这里结束：

return {min (left_one),(right_one)}
     = {min (0), (0) }
     = 0

但这显然是错误的，因为这个节点 (4) 不是叶节点。您的代码忘记计算当前节点（哎呀！）。我相信你可以设法解决这个问题。

现在，实际上，您执行此操作的方式并不是最快的，但我不确定这是否与此练习相关。考虑这棵树：

         4
       3   5
     2
   1

您的算法将递归地计算左分支，即使如果您首先计算右分支并注意到 3 有左分支，它可能会退出，因此它明显长于 5（即叶子）。但是，当然，首先计算正确的分支并不总是有效的！

相反，使用更复杂的代码，并且可能以更大的内存使用为代价，您可以从左到右、从上到下（就像英语阅读顺序一样）检查节点并在找到的第一页停止。

于 2009-08-28T04:20:18.763 回答
0

您创建的内容可以被认为是深度优先搜索。但是，鉴于您所追求的（最短的分支），这可能不是最有效的方法。考虑一下您的算法将如何在左侧（根节点的）非常重但右侧只有一个节点的树上执行。

提示：考虑广度优先搜索方法。

于 2009-08-28T04:19:06.160 回答
0

你在那里的东西看起来像一个深度优先搜索算法，在你想出一个解决方案之前必须搜索整个树。您需要的是广度优先搜索算法，它可以在找到解决方案后立即返回，而无需进行完整搜索

于 2009-08-28T04:19:55.003 回答