计算 C 上的 BST 级别

Question

有一种递归方法来计算级别，这很相似，但不起作用。我的错误是哪一个？

struct s_node
{
  struct s_node * left;
  struct s_node * right;
  int value;
}
typedef struct s_node * t_node;
int levels (t_node tree)
{
  if(tree != NULL)
  {
    return 1+levels(tree->left)+levels(tree->right);
  }
  else
       return 0;
}

Answer 1

这会计算节点总数。如果您想“计算级别”(我假设这意味着您想确定树的高度)，您可以将代码修改为如下所示:

int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}

int levels (struct s_node * tree)
{
    if (tree != NULL)
    {
        return 1 + max(levels(tree->left), levels(tree->right));
    }
    else 
        return 0;
}

请注意，其中可能仍然存在 C 错误，我已经很多年没有使用 C 了，但是您应该了解算法的想法。