什麼是最優化的遍歷樹的算法（方法）？

Question

正如維基百科中所述，有多種遍歷樹數據結構的算法。但是其中一些算法是其他算法的組合，比如雙向搜索對其他圖形而非樹木幾乎有用。但是對於一棵樹，我們幾乎不知道樹的結尾，我們只能從根開始或從其子開始。

在這種情況下，我們也許能夠納入搜索過程中多或多線程。但我找不到任何綜合的方法來描述這一點。

現在我的問題是，基本上什麼是遍歷樹的最優化的方式，當我們不能夠訪問整個數據結構（能夠對其進行索引，等等類似的文件目錄）？

Answer 1

嘗試在二叉搜索樹的序遍歷。搜索的複雜度是nlogn，遍歷是n，這被認爲是最好的。

例：http://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Answer 2

最優化的算法通常是一個特定用例和平臺進行了優化。

不要緊，你是否做序，序或後序。或者您是否執行DFS或BFS。 重要的是：

• 樹有多大？它是否適合記憶？
• 樹有多深？你可以使用遞歸，還是你必須使用顯式的單獨堆棧？
• 你如何找到節點的孩子。你必須訪問硬盤/網絡？
• 在遍歷中找到之後，您想如何處理節點。如果這個操作足夠長，優化遍歷是不值得的。
• 你如何在線程之間共享數據？
• 樹中的節點是如何分佈的？它是否類似於均勻分佈，還是有一些非常長和一些很短的分支？
• 節點密鑰有多大（這會影響數據的局部性以及您可以將多少數據放入一個L1/L2緩存行）？