C-如何在N叉樹中找到給定深度的節點數？-有解無憂

我試圖在 N 元樹中找到給定深度的節點總數，但我被卡住了。

這是資料結構：

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

typedef NTree_node *NTree;

以下函式應該遞回遍歷樹并回傳一個非負整數：

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);
}

它運行但不回傳正確的輸出，因為它基于僅適用于二叉樹的類似函式。

關于我可以改進或改變的任何提示？我想我并沒有真正理解什么是正確的程式。

uj5u.com熱心網友回復：

有幾個問題：

在第二次遞回呼叫中：
```
int right = NTree_depth_nodes(T->sibling, depth - 1);
```
...錯誤的深度作為引數傳遞。當您呼叫同級時，不應減小depth引數的值：同級處于相同深度。所以改為：
```
int right = NTree_depth_nodes(T->sibling, depth);
```
當depth為零時，您不應立即回傳：可能有兄弟姐妹要檢查，這會增加計數。

這是一個更正：

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.

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395972.html

標籤：C 算法树二进制二叉树

上一篇：使串列盡可能無序的函式

下一篇：該程序如何在分支總和python代碼中實際流動