紅黑樹的內部路徑長度

我正在研究一個家庭作業問題，要求我們查找紅黑樹的內部路徑長度。這是迄今爲止我已經實現的代碼。紅黑樹的內部路徑長度

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

我想我錯過了遞歸的基本情況。有人能幫助我更好地理解它嗎？謝謝。

來源

2016-03-26 Nivetha Mahalakshmi

如果沒有條件匹配，則返回一個未初始化的值'int ipl;'。 –

@πάνταῥεῖ。我修正了這一點。我似乎還沒有解決這個問題。我相信這與將根節點分配給BLACK有關。我不確定這是否是正確的做法。 –

我認爲正確的答案是，我們不必檢查根節點的顏色是黑色的。應該爲黑色和紅色節點計算內部路徑長度。如果我們不考慮紅色鏈接，這意味着我們正在考慮通過紅色鏈接連接的元素作爲兩個節點，事實並非如此。

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

來源

2016-03-28 15:33:07

紅黑樹的內部路徑長度

回答

相關問題