樹遍歷 - 從只有父指針的樹葉開始？

概念上是否有可能通過從給定葉節點（而不是根節點）開始遍歷樹並使用父指針到達根？樹遍歷 - 從只有父指針的樹葉開始？

我問這個，因爲我看到有人實現了一棵樹，他們使用一個數組來保存所有葉節點/外部節點，並且每個葉/外部節點只指向它們的父節點，並且這些父指向父節點節點等，直到你到達沒有父母的根節點。因此，它們的實現將要求您從其中一個樹葉開始到達樹中的任何位置，並且因爲樹節點沒有任何子指針，只有父指針，所以不能「下」樹。

我發現這個實現很有趣，因爲我沒有看到任何類似的東西，但我很好奇它是否仍然可以被認爲是「樹」。我從來沒有見過一棵樹開始遍歷樹葉，而不是根。我也從來沒有見過一棵樹，樹節點只有父指針而沒有子指針。

來源

2013-03-11 user2157871

你基本上已經回答了你自己的問題。是的，它完全可以這麼做。 Windows Presentation Foundation是一個很好的例子*你爲什麼要這樣做;即相對數據綁定;即遍歷樹，直到找到某物，然後綁定它。請參閱：http://stackoverflow.com/questions/84278/how-do-i-use-wpf-bindings-with-relativesource更有趣的問題是*爲什麼*你想，爲什麼你只想要_parent_鏈接。 – 2013-03-11 17:45:33

是的，這個結構存在。它通常被稱爲。

意大利麪條棧對於表示「是關係的一部分」很有用。例如，如果要以使上傳效率更高的方式來表示類層次結構，則可以將類層次結構表示爲意大利麪條堆棧，其中每個類型的節點將存儲指向其父類型的指針。這樣，通過從節點向上走，很容易找到上傳是否有效。

它們還經常用於編譯器來跟蹤範圍信息。每個節點代表程序中的一個作用域，每個節點都有一個指向表示其上一級作用域的節點的指針。

希望這會有所幫助！

來源

2013-03-11 18:02:33 templatetypedef

如果給出葉節點的數組A，則遍歷是可能的。如果只給出一個葉節點，我不知道如何遍歷樹。僞代碼：

// initial step 
add all nodes in A to a queue Q 

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q

來源

2013-03-11 18:02:35 Bhaskar

樹遍歷 - 從只有父指針的樹葉開始？

回答

相關問題