二元樹節點保持對其父項的引用

二叉樹中的節點是否保留對其父項的引用是「傳統的」（或「道德的」）？二元樹節點保持對其父項的引用

通常情況下，我不這麼認爲，僅僅因爲樹是有向圖，所以PARENT-> CHILD鏈接定義的事實不應該意味着CHILD ---> PARENT也被定義。換句話說，通過保持對父代的引用，我們會以某種方式破壞樹的語義。

但我想知道人們在想什麼？

我問，因爲我有一個問題找到樹中兩個給定節點的最低公共父親。如果每個節點都有對父節點的引用，那麼這個問題將非常容易解決，但這就像是作弊！

謝謝

來源

2013-05-17 One Two Three

如何實現二叉樹應該取決於您的需求。

如果您的應用程序需要遍歷葉子到樹幹的方向，那麼最好的方法是實現對父節點的引用。

我發現最好將您的數據結構適合您的需求，而不是嘗試與其他邏輯做出解決方法。畢竟，爲什麼樹必須是有向圖？使它具有針對性是一個具體的實現，非常類似於一個列表及其具體實現，如單向或雙向鏈表。

來源

2013-05-17 17:24:55

它仍然可以是所有權的有向圖。請看下面的節點：

template <typename T> 
struct node 
{ 
    T data_; 
    std::unique_ptr<node> left_child_; // I own my children. 
    std::unique_ptr<node> right_child_; 
    node* parent_; // Just lookin' at my parent. 
};

正如史蒂芬邁耶上面所說的，它真的不是作弊：建立數據結構來解決你的問題，不用擔心它的道德:-)

來源

2013-05-17 19:30:40 bstamour

二元樹節點保持對其父項的引用

回答

相關問題