一棵榕树的高度

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 然后应该得到它的每个子树的高度，并保留这些值中的最大值。就是returns这个最大值+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;
}

一棵榕树的高度

Height of a k ary tree

c

tree

recursion