有效的方法來遍歷對象樹？

Question

我有一組TreeNodes，每個TreeNode都有一個id，一組父節點和一組子節點。

對於給定的節點ID，我正在尋找一種有效的方式來生成所有通過該節點的鏈接。簡而言之，從節點開始，遍歷所有子節點。如果一個節點有多個孩子，爲每個孩子創建一個鏈接。遍歷孩子等。

我也希望能夠通過父節點在'向上'的方向做到這一點。

有沒有一個簡單的算法來做到這一點？

編輯：哦，我想能夠輸出在給定鏈中的所有節點的ID的...

Answer 1

你正在尋找一個Breadth First或Depth First Search。起初它不超過以下內容（這是深度優先搜索）。

Visit(Node node) 
{ 
    foreach (Node childNode in node.Children) 
    { 
     Visit(childNode); 
    } 

    DoStuff(node); 
} 

問題是該圖可能包含循環，因此該算法將進入無限循環。爲了解決這個問題，你必須記住訪問過的節點，方法是將它們放在一個集合中。如果圖形沒有循環 - 例如如果它是一棵樹 - 這個簡短的算法已經可以工作。

順便說一句，如果TreeNode有多個父節點，它不是一棵樹，而是一個圖節點。

Answer 2

嘛，如果節點對其父的引用，它的簡單如果沒有這樣的引用，比你可以使用寬度優先的搜索，爲了獲得父節點（一旦在樹中，每個節點只有一個（或根本沒有，如果它是一個根目錄的話）parent。

例如，初始設置您的父節點集合。

- 編輯 -

一旦一個節點可能有多個父節點，那麼你正在處理一個圖。也有graph traversal algorithms（見旁邊的表格）。

確保，如果你的圖有一個週期，你會不會落得具有無限循環

Answer 3

你可能想看看depthFirstEnumeration()和breadthFirstEnumeration()在DefaultMutableTreeNode。然而，這並不能解決你想以自下而上的方式瀏覽樹的問題。