红黑树内部路径长度

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

我认为正确答案是我们不必检查根节点的颜色是否为黑色。应该为黑色和红色节点计算内部路径长度。如果我们不考虑红色 link，这意味着我们正在将由红色 link 连接的元素视为一个二节点，事实并非如此。

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));
  }

红黑树内部路径长度

Internal path length of red black tree

c++

recursion

red-black-tree