二叉树-在一个级别上计数节点 [英] Binary Tree - Counting nodes on a level
问题描述
我正在编写一个二叉树类,并且被困在levelCount方法上,该方法需要计算树级别上的节点数.该类和方法如下所示:
I'm writing a binary tree class, and I'm stuck on a levelCount method, where I need to count the number of nodes on a level of the tree. The class and method look something like this:
public class ConsTree<T> extends BinaryTree<T>
{
BinaryTree<T> left;
BinaryTree<T> right;
T data;
public int levelCount(int level)
{
}
}
因此,想法是每棵树在其左侧都有一棵树,在其右侧有一棵树以及数据.有一个抽象类binarytree和子类ConsTree和EmptyTree.
So the idea is that each tree has a tree to its left, a tree to its right, and data. There is an abstract class binarytree and subclasses ConsTree and EmptyTree.
我认为我需要使用广度优先搜索并在达到该级别后计算节点数,但是我对如何开始一无所知.这里的任何指导都会有所帮助.我可以提供任何其他必要的信息.
I think I need to use a breadth first search and count the number of nodes once I get to that level, but I'm stuck on how to start. Any guidance here would be helpful. I can provide any other info necessary.
推荐答案
以下是一般方法.
您可以像平常一样遍历树(深度优先,顺序排列),但是您也可以通过伪代码简单地传递所需的和实际的级别,例如:
You traverse the tree exactly as you would normally (depth-first, in-order) but you simply pass down the desired and actual level as well, with pseudo-code such as:
def getCountAtLevel (node, curr, desired):
# If this node doesn't exist, must be zero.
if node == NULL: return 0
# If this node is at desired level, must be one.
if curr == desired: return 1
# Otherwise sum of nodes at that level in left and right sub-trees.
return getCountAtLevel (node.left, curr+1, desired) +
getCountAtLevel (node.right, curr+1, desired)
#######################################################################
# Get number of nodes at level 7 (root is level 0).
nodesAtLevel7 = getCountAtLevel (rootNode, 0, 7)
它实际上并没有遍历 entire 树,因为一旦到达所需的级别,它就可以忽略其中的所有内容.这是一个完整的C程序,展示了这一点:
It doesn't actually traverse the entire tree since, once it gets to the desired level, it can just ignore everything underneath that. Here's a complete C program that shows this in action:
#include <stdio.h>
typedef struct _sNode { struct _sNode *left, *right; } tNode;
// Node naming uses (t)op, (l)eft, and (r)ight.
tNode TLLL = {NULL, NULL }; // level 3
tNode TLLR = {NULL, NULL };
tNode TRLL = {NULL, NULL };
tNode TRLR = {NULL, NULL };
tNode TRRR = {NULL, NULL };
tNode TLL = {&TLLL, &TLLR }; // level 2
tNode TRL = {&TRLL, &TRLR };
tNode TRR = {NULL, &TRRR };
tNode TL = {&TLL, NULL }; // level 1
tNode TR = {&TRL, &TRR };
tNode T = {&TL, &TR }; // level 0 (root)
static int getCAL (tNode *node, int curr, int desired) {
if (node == NULL) return 0;
if (curr == desired) return 1;
return getCAL (node->left, curr+1, desired) +
getCAL (node->right, curr+1, desired);
}
int main (void) {
for (int i = 0; i < 5; i++) {
int count = getCAL(&T, 0, i);
printf ("Level %d has %d node%s\n", i, count, (count == 1) ? "" : "s");
}
return 0;
}
它将构建以下形式的树(其中T
表示顶部,L
是左分支,而R
是右分支):
It builds a tree of the following form (where T
means top, L
is a left branch and R
is a right branch):
______T______ (1 node)
/ \
TL TR (2 nodes)
/ / \
TLL TRL TRR (3 nodes)
/ \ / \ \
TLLL TLLR TRLL TRLR TRRR (5 nodes)
(0 nodes)
如果编译并运行该代码,您会看到它在每个级别提供了正确的节点数:
If you compile and run that code, you'll see it gives the correct node count at each level:
Level 0 has 1 node
Level 1 has 2 nodes
Level 2 has 3 nodes
Level 3 has 5 nodes
Level 4 has 0 nodes
这篇关于二叉树-在一个级别上计数节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!