C++二進制搜索樹 - 複雜類型

Question

我需要爲2種類型的對象實現BST;賬戶和客戶。這兩種類型都有一個PK（都稱爲「ID」）。 當我在Google /研究解決方案時，我可以找到許多BST解決方案，但它們似乎都適用於簡單的類型，例如BST解決方案可以對{1,2,3,4,99，... 999}等整數進行排序 - 但我希望BST解決方案根據其pk對複雜類型/類進行排序。這是可能的/任何提示？謝謝。

Answer 1

用於構建整數二叉查找樹的邏輯應該可以立即推廣到其他數據類型。而不是在每個節點中存儲一個整數作爲鍵，而是將您的客戶和帳戶名稱存儲在每個字段中，但是在查找時只比較主鍵。這真的應該是那麼簡單。

也就是說，除非這是作業分配，否則應該使用std :: map，它具有二叉搜索樹的所有複雜性保證，但已經爲您編寫，廣泛使用且經過嚴格測試。

希望這會有所幫助！

Answer 2

一種方法是修改您的節點定義，添加對您想要存儲的對象的引用並設置一個索引（在您的案例中爲pk），對這些註釋進行排序。在使用不同類型，模板可以解決：

class Account 
{ 
    public: 
     Account(int k) : pk(k) {}; 
     int pk; 
    /* ... */ 
}; 


template<typename T> 
class TreeNode 
{ 
    public: 
     TreeNode(T& the_object) : id(the_object.pk), object(the_object) {}; 

     int id; 
     T& object; 
}; 


int main() { 
    Account a(9); 
    TreeNode<Account> tn(a); 
    std::cout << tn.id; 
} 

如果你想在一棵樹混合不同的對象類型，另一種是定義包含一個訪問到的PK屬性的類，使賬戶和客戶所固有它，例如：

class Indexable 
{ 
    public: 
     Indexable(int the_pk) : pk(the_pk) {}; 
     int pk; 
}; 

class Account : public Indexable 
{ 
    public: 
     Account(int k) : Indexable(k) {}; 
    /* ... */ 
}; 

class TreeNode 
{ 
    public: 
     TreeNode(Indexable& the_object) : id(the_object.pk), object(the_object) {}; 

     int id; 
     Indexable& object; 
}; 


int main() { 
    Account a(9); 
    TreeNode tn(a); 
    std::cout << tn.id; 
} 

正如其他答案指出，在生產中，你可能會考慮使用std :: map或另一個已知的樹結構庫。