c - 一棵榕树的高度

Question

我正在尝试实现一个计算 k 叉树高度的函数。我的树结构是这样的:

struct node {
    int kids_num;
    int data;
    struct node **kids;
};

功能:

int height(struct node *root)
{
     if (root == NULL)
         return -1;

     for (int i = 0; i < root->kids_num; i++)
     {
          height(...)
     }

     return ??
}

你能帮我解决这个函数的其余部分吗？

Answer 1

一棵树的高度，是其子树高度的最大值+1。 没有子树的树的高度为1。

然后，函数 height 应该获取其每个子树的高度，并保留这些值中的最大值。它返回这个最大值 + 1。

int height(struct node *root)
{
     if (root == NULL)
         return -1;

     int maxHeight = 0;
     for (int i = 0; i < root->kids_num; i++)
     {
          int h = height(root->kids[i]);
          if (h > maxHeight)
              maxHeight = h;
     }
     return maxHeight + 1;
}