具有给定级别的节点的二叉树数量

我需要编写一个程序来计算从二进制树中给定的某个级别的节点数量。具有给定级别的节点的二叉树数量

我的意思是< numberofnodes（INT级）{}>

我想没有任何成功写它，因为我没有怎么去到一定水平，然后去计算节点的数量。

来源

2010-05-17 sadatwins

这是家庭作业3级节点的数量？你到目前为止尝试过什么？ – Johnsyweb 2010-05-17 22:03:07

@Johnsyweb - 这听起来像是对我功课 – 2010-05-17 22:03:22

如果这是家庭作业，标记为这样。你尝试做什么？ – Rubys 2010-05-17 22:03:31

嗯，有很多方法可以做到这一点。最好的办法是有一个单维数组，用于跟踪每个级别添加/删除的节点数量。考虑到你的要求是最简单的方法。

但是，如果只提供了一个二叉树，则必须遍历并进入许多级别并对节点进行计数，但我没有看到任何其他选择。

要达到某个级别，通常需要一个名为'current_depth'的变量，它将跟踪您所处的级别。一旦达到您的兴趣级别并且节点被访问一次（通常a为了遍历就足够了）你可以增加你的计数。希望这有助于。

来源

2010-05-17 22:04:07 bragboy

可以ü发表一些代码示例 – sadatwins 2010-05-17 22:05:35

虽然它不直接回答你的问题，你可以用它作为参考：http://www.technicalypto.com/2010/02/trace-path-of-binary-tree。 html – bragboy 2010-05-17 22:25:00

使用递归函数只能下降到一定的水平。

来源

2010-05-17 22:05:41 tamasd

我认为OP是要求**从**某个级别，而不是**到**某个级别。 – 2010-05-17 22:19:52

我认为OP要求**在某个级别**，但谁知道。 – sth 2010-05-17 22:31:17

我假设你的二叉树不一定是完整的（即，不是每个节点都有两个或零个子节点，或者这变得微不足道）。我还假设你应该只计算某个级别的节点，而不是该级别或更深的节点。

有很多方法可以做你要求的东西，但是你可以把它想象成一个图搜索问题 - 给你一个起始节点（树的根节点），一种遍历边的方法（孩子链接）和一个标准 - 距根的一定距离。

在这一点上，你可能学习了图搜索算法 - 哪种算法听起来很适合你的任务？

来源

2010-05-17 22:05:49 Uri

一般条款：
递归。
在递归的每一次迭代中，你都需要测量你在什么级别上，因此要知道你需要超出目前的位置。
递归部分：

你是什么情况？你在什么条件下说“好吧，时间停止递归”？
如何在没有任何全局计数的情况下计算递归中的某些内容？

来源

2010-05-17 22:07:32 Rubys

我认为最简单的方法是简单地跟随树的递归性质，使用累加器来跟踪当前级别（或者可能还有待下降的级数）。

该函数的非递归分支是当您遇到有问题的级别时。此时你只需返回1（因为你在该级别找到了一个节点）。

递归分支，简单地总结从左和右递归调用返回的该级别的节点数量。

来源

2010-05-17 22:10:03

这是伪代码，这是假定根具有0

int count(x,currentLevel,desiredLevel) 
    if currentLevel = desiredLevel 
     return 1 
    left = 0 
    right = 0 
    if x.left != null 
     left = count(x.left, currentLevel+1, desiredLevel 
    if x.right != null 
     right = count(x.right, currentLevel+1, desiredLevel 
    return left + right

水平因此，要获得你打电话

count(root,0,3)

来源

2010-05-17 22:56:19 Enrique

具有给定级别的节点的二叉树数量

回答

相关问题