赤い黒い木の内部のパスの長さ

Question

私は赤い黒い木の内部パスの長さを見つけるように頼む宿題の問題に取り組んでいます。これはこれまで実装していたコードです。

int Tree::internalpathlength(BinTree* root_node, int curr_level){ 
int ipl; 
if(root_node == NULL){ 
    return 0; 
} 
else if(root_node->colour == BLACK){ 
    ipl = (curr_level+internalpathlength(root_node->left,curr_level+1)+internalpathlength(root_node->right,curr_level+1)); 

} 
return ipl; 
} 

私は再帰の基本ケースがないと思います。誰かが私がそれをよりよく理解するのを助けることができるかおかげさまで

Answer 1

私は、ルートノードの色が黒であることを確認する必要はないと考えています。内部パス長は、黒と赤のノードの両方で計算する必要があります。 赤いリンクを考慮しないと、赤いリンクで2つのノードに接続されている要素が考えられますが、そうではありません。

int Tree::internalpathlength(BinTree* root_node, int curr_level){ 
    if(root_node == NULL){ 
    return 0; 
    } 
    else 
     return (curr_level+internalpathlength(root_node->left,curr_level+1)+internalpathlength(root_node->right,curr_level+1)); 
    }