問題繼承BST到黑紅樹

由於黑紅樹是二叉搜索樹，我決定使用繼承來實現。下面是如何在我的代碼中看到短節點繼承：問題繼承BST到黑紅樹

struct BST_node 
{ 
    // public interface here 

    int key; 
    BST_node* left; 
    BST_node* right; 
    BST_node* parent; 
}; 

struct BRT_node : BST_node 
{ 
    // public interface here 

    NodeColour colour; 
};

問題我遇到過這個問題，派生類中的指針是基類的類型。因此，我不能在沒有顯式強制轉換的派生類中使用它們。也許隱藏成員和使用虛擬訪問器方法可以做到這一點，但這會破壞這種簡單的語法：

node-> left = node-> parent;

有沒有更好的方法來做到這一點？

來源

2011-03-05 Nefarel

這是（幾乎）普遍用C++中的模板完成的原因。至少在C++中實現時，繼承對此任務不起作用。爲此目的使用繼承的唯一方法是定義一個抽象接口，並且實現完全在派生類中。 – 2011-03-05 16:47:26

您不能將平衡未知的BST節點插入紅黑樹中，但擬議的結構似乎暗示它是允許的。這就是尷尬演員的來源。 – aaz 2011-03-05 17:18:53

將所有數據成員放入BRT_node有什麼不對？

struct BRT_node 
{ 
    int key; 
    BRT_node* next; 
    BRT_node* prev; 
    BRT_node* parent; 
    NodeColour colour; 
};

這樣，你就可以保持node->left = node->parent;的「好語法」。

這裏使用繼承的問題是因爲紅黑樹算法需要BRT_node s，而不是BST_node s。所以在這種情況下繼承是不合適的。

來源

2011-03-05 17:19:55

問題繼承BST到黑紅樹

回答

相關問題