递归计算通用树节点高度的C代码问题排查

我正在完成一项技术挑战：实现函数height(n, T)，返回通用树T中节点n的高度。该树通过两个数组存储：一个数组存储节点标签，另一个存储父节点索引（值为-1表示该节点是根节点）。我编写的C递归代码部分用例计算结果正确，但部分用例不符，例如根节点0的预期高度为4，实际输出为3。

完整代码 #

#include<stdio.h>
#define MAXLENGTH 100
#define NULL_NODE -1
 
typedef int Node;
typedef char LabelType;
 
typedef struct {
    Node      P[MAXLENGTH];
    LabelType L[MAXLENGTH];
    int maxNode;
} Tree;

Node leftmostChild(Node n, Tree *pT){
    if ( n < 0 || n > pT->maxNode) return NULL_NODE;
    for ( Node i = n + 1; i <= pT->maxNode; i++){
        if ( pT->P[i] == n )  return i;
    }
    return NULL_NODE;
}

Node rightSibling(Node n, Tree *pT){
    if ( n < 0 || n > pT->maxNode) return NULL_NODE;
    for ( Node i = n + 1; i <= pT->maxNode; i++){
        if ( pT->P[i] == pT->P[n] )  return i;
    }
    return NULL_NODE;
}
 
int height(Node n, Tree *pT){
    if ( n < 0 || n>pT->maxNode) return -1;
    if ( leftmostChild(n, pT) == NULL_NODE && rightSibling(leftmostChild(n,pT),pT) == NULL_NODE) return 0;
    int L = height(leftmostChild(n,pT), pT);
    int R = height(rightSibling(leftmostChild(n,pT), pT), pT);
    if ( L > R) return L + 1;
    return R + 1;
}
 
int main(){
    Tree T = { {-1, 0, 0, 0, 0, 0, 3, 6, 2, 5, 1, 10, 9, 4, 7, 5},
    {'S', 'L', 'K', 'J', 'A', 'V', 'R', 'E', 'F', 'T', 'C', 'X', 'U', 'I', 'H', 'D'}, 15};
    for (int i = 0; i <= T.maxNode; i++)
        printf("height(%d) = %d\n", i, height(i, &T));
    }

预期输出 #

height(0) = 4
height(1) = 2
height(2) = 1
height(3) = 3
height(4) = 1
height(5) = 2
height(6) = 2
height(7) = 1
height(8) = 0
height(9) = 1
height(10) = 1
height(11) = 0
height(12) = 0
height(13) = 0
height(14) = 0
height(15) = 0

当前错误输出 #

height(0) = 3
height(1) = 2
height(2) = 1
height(3) = 3
height(4) = 1
height(5) = 2
height(6) = 2
height(7) = 1
height(8) = 0
height(9) = 1
height(10) = 1
height(11) = 0
height(12) = 0
height(13) = 0
height(14) = 0
height(15) = 0

问题分析与修复 #

问题根源 #

当前height函数仅比较了节点的左孩子和左孩子的第一个右兄弟的高度，没有遍历节点的所有子节点。以根节点0为例，它的子节点有1、2、3、4、5，其中节点3的高度是3，是所有子节点中最高的，但当前代码只计算了节点1和2的高度，取最大值加1，导致根节点高度少算了1（3+1=4才是正确值，当前算的是2+1=3）。

修复后的height函数 #

修改逻辑为遍历节点的所有子节点，记录最大高度，最终返回最大高度+1：

int height(Node n, Tree *pT){
    if (n < 0 || n > pT->maxNode) return -1;
    
    int max_child_height = -1;
    Node child = leftmostChild(n, pT);
    
    // 遍历所有子节点，找到最高的子节点高度
    while (child != NULL_NODE) {
        int child_h = height(child, pT);
        if (child_h > max_child_height) {
            max_child_height = child_h;
        }
        child = rightSibling(child, pT);
    }
    
    // 如果没有子节点，高度为0；否则为最高子节点高度+1
    return max_child_height == -1 ? 0 : max_child_height + 1;
}

修复说明 #

1. 初始化max_child_height为-1，表示初始没有找到子节点
2. 通过leftmostChild获取第一个子节点，然后循环调用rightSibling遍历所有子节点
3. 对每个子节点递归计算高度，更新最大子节点高度
4. 没有子节点时返回0，否则返回最大子节点高度+1，符合树高度的定义（叶子节点高度为0，非叶子节点高度为子树最大高度+1）

内容的提问来源于stack exchange，提问作者Dintel