C - 如何找到 N 叉树中给定深度的节点数？

Question

我试图找到 N 叉树中给定深度处的节点总数，但我卡住了。

这是数据结构：

typedef struct elem2 {
  int value;
  struct elem2 *firstChild;
  struct elem2 *sibling;
} NTree_node;

typedef NTree_node *NTree;

以下函数应该递归遍历树和return一个非负整数：

int NTree_depth_nodes(NTree T, int depth) {
  if (T == NULL) {
    /* empty tree -> depth is 0 */
    return 0;
  }
  if (depth == 0) {
    /* depth 0 means we only have the root */
    return 1;
  }

  int left = NTree_depth_nodes(T->firstChild, depth - 1);
  int right = NTree_depth_nodes(T->sibling, depth - 1);

  return 1 + (left + right);
}

它可以运行，但 return 没有正确的输出，因为它基于仅适用于二叉树的 similar function。

有什么可以改进或更改的提示吗？我想我不太了解什么是正确的程序。

Answer 1

有几个问题：

在第二次递归调用中：
```
int right = NTree_depth_nodes(T->sibling, depth - 1);
```
...错误的深度作为参数传递。在调用 sibling 时，不应减小 depth 参数的值：兄弟节点处于相同深度。所以改为：
```
int right = NTree_depth_nodes(T->sibling, depth);
```
当 depth 为零时，您不应该立即 return：可能有兄弟姐妹要检查，这会增加计数。

这里更正：

int NTree_depth_nodes(NTree T, int depth) {
  if (T == NULL) {
    /* empty tree -> depth is 0 */
    return 0;
  }

  int count = 0;
  if (depth == 0) {
    /* depth 0 means we have a node at the intended level */
    count++;
  }

  count += NTree_depth_nodes(T->firstChild, depth - 1);
  count += NTree_depth_nodes(T->sibling, depth);

  return count;
}

我使用以下驱动程序代码测试了这段代码：

NTree node(int value) {
    NTree n = malloc(sizeof(NTree_node));
    n->sibling = NULL;
    n->firstChild = NULL;
    n->value = value;
    return n;
}

int main(void) {
    /* Create this tree:
             1
           / | \
          2  3  4
            /|  |\
           5 6  7 8
                |
                9
    */
    NTree root = node(1);
    root->firstChild = node(2);
    root->firstChild->sibling = node(3);
    root->firstChild->sibling->sibling = node(4);
    root->firstChild->sibling->firstChild = node(5);
    root->firstChild->sibling->firstChild->sibling = node(6);
    root->firstChild->sibling->sibling->firstChild = node(7);
    root->firstChild->sibling->sibling->firstChild->sibling = node(8);
    root->firstChild->sibling->sibling->firstChild->firstChild = node(9);

    for (int depth = 0; depth < 5; depth++) {
        printf("At depth %d there are %d nodes.\n", depth, NTree_depth_nodes(root, depth));
    }
    return 0;
}

输出为：

At depth 0 there are 1 nodes.
At depth 1 there are 3 nodes.
At depth 2 there are 4 nodes.
At depth 3 there are 1 nodes.
At depth 4 there are 0 nodes.

C - 如何找到 N 叉树中给定深度的节点数？

C - How to find number of nodes at given depth in a N-ary tree?

c

algorithm

binary

tree

binary-tree