在深度为 k 且分支因子为 n 的树中查找可能的最大和最小节点
我有一棵深度为 k 、分支因子为 n 的树。我一直在尝试找到一个通用公式：
- 此树中可能的最大节点数
- 此树中可能的最小节点数
有什么建议吗？ 提前致谢。
I have a tree of depth k and branching factor of n. I've been trying to find a general formula for:
- Maximum number of nodes possible in this tree
- Minimum number of nodes possible in this tree
Any suggestions?
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我不想这么说，但对于数据结构课程来说，这是一个非常简单的问题。我不想表现得粗鲁或刻薄或任何类似的事情，但这就是这些问题所得到的最简单的问题。
但你要求的是建议，而不是解决方案。这是一件好事。 :-)
我首先要确保您了解分支因子的定义。然后我会为 k,n 选择几个简单的值，例如 (1,1) (2,2) (3,2) 并查看结果是什么。我向你保证，一种模式将会出现！
编辑：
所以你已经掌握了分支因素。让我们看看最小值。
如果你的深度为 k，你知道你可以沿着 k 个不同的节点遍历，对吗？因此，如果这些节点都没有任何其他子节点，并且结束节点也没有子节点，那么您对那里的节点有何看法？
好吧，这很容易。最大值有点难，但仍然相当简单。最简单的看待它的方法就是不要像树一样思考。树有顶，也有下。相反，可以将其视为一系列同心圆，每个圆代表一个深度。
让我们从（深度 = 1）开始。您知道您将只有一个节点，对吗？我的意思是它不能有任何孩子，因为深度仅限于 1！现在，让我们看看深度为 2。起始节点可以有 n 个（假设 n 是分支因子）子节点。因此，这将是 n + 1。
现在，如果我们再添加一个，我们最终会在“外环”上得到 n 个节点，每个节点可以有 n 个子节点。所以你最终得到 n*n + n + 1。
在每个连续的环上，你最终得到 (上次添加的节点) * (分支因子) + 所有现有节点。现在你能想出一种方法将其表达为公式吗？
I hate to say it, but this is a trivially simple question for a data-structures course. I don't want to be rude or mean or anything of the sort, but this is about as simple as these questions get.
But you asked for suggestions, not solutions. This is a good thing. :-)
I would start with making sure you know the definition of branching factor. Then I would draw a pick a couple easy values for k,n like (1,1) (2,2) (3,2) and see what the result is. I promise you a pattern will emerge!
Edit:
So you have a grasp of the branching factor. Let's look at the minumum.
If you have a depth of k, you know that you can traverse along k different nodes right? So if none of those nodes have any other children, and the end node has no children, what can you say about the nodes there?
Okay that was easy. The maximum is a bit harder, but still fairly straightforward. The easiest way to look at it is to think less like a tree. Trees have a top and go down. Instead, think of this as a series of concentric circles, each circle representing a level of depth.
Let's start with (depth = 1). You know you're going to have just one node, right? I mean it can't have any children, because you're limited to 1 depth! Now, let's look at depth of 2. The starting node can have n (assuming n is the branching factor) child nodes. So that would be n + 1.
Now if we add one more to that, we end up with n nodes on the "outside ring" each of which can have n children. So you end up with n*n + n + 1.
On each successive ring, you end up with (nodes added last time) * (branching factor) + all existing nodes. Now can you think of a way to express that as a formula?
为了计算最大节点数，假设每个新级别都已满。
在第一个级别中，您有 1 个节点，在第二个 n 个节点中，在第三个中，您有 n^2 个节点（n 代表前 n 个节点），在第四个节点中，您有 n^3 个节点（n 代表前 n 个节点） ^2)...
这给你 sum(i=1, k-1, n^i) + 1 ==> (n(n^k -1))/(n-1) + 1
最小节点数当然是 0 :)
To calculate the max number of nodes assume every new level is full.
In the first level you have 1 node, in the second n nodes, in the third you have n^2 nodes (n for each of the previous n), in the fourth you have n^3 (n for each of the previous n^2)...
This gives you sum(i=1, k-1, n^i) + 1 ==> (n(n^k -1))/(n-1) + 1
The min number of nodes is of course 0 :)