樹上的算法。有幫助指出有效解決方法的提示嗎？

我正在做CS基本面和算法的重新上限。樹上的算法。有幫助指出有效解決方法的提示嗎？

我想確保我得到了正確的東西。

當我讀取提示像bottom-up和top-down等我是否正確，他們總是應採取如下？
bottom-up - >post-order traversal
top-down - >pre-order traversal
??? - >in-order traversal

我不清楚什麼樣的暗示將意味着一箇中序遍歷;
此外，還有一個提示比這更多的完整列表提示？
我的意思是也許還有其他提示指向迭代，而不是遞歸，例如？

我在想，如果我能以某種方式分類，這樣它會幫助我解決算法問題要容易得多

任何輸入的高度讚賞。

來源

2012-03-18 Cratylus

也許是從左到右的遍歷？ – nullpotent 2012-03-18 09:32:49

在搜索樹的情況下是（排序）順序，因此名稱。 – Raphael 2012-03-18 10:14:55

他們不是一回事。想象一下，你有一個加括號的表達式，已經解析成一棵樹，你需要打印出來。如果你想用後綴表示法（2 2 +）來顯示它，你會做後續遍歷。要以中綴表示法（2 + 2）顯示它，請按順序遍歷。但是如果你想計算表達式的值，不管你如何顯示它，最簡單的做法是先深度優先和自下而上。

由於您要求提供更多的指導來源，我建議您尋找解釋原則的教科書或在線資源。解決問題是很好的，但有時可以從大局出發很好。恐怕我不知道有什麼好的建議。

來源

2012-03-18 09:39:18 alexis

可能是我誤解了你的答案，但是在你的例子中'post'和'in'是提示，你遵循相應的方法？ – Cratylus 2012-03-18 09:51:20

我確定他們是暗示，但「相應的方法」不是自下而上或自上而下的。這是後序或按順序。 – alexis 2012-03-18 09:58:50

所以你在說'後綴' - >'後序'而不是'自下而上'，除了提到的那個還有其他提示嗎？你的意思是我寫的OP意味着像'postfix'映射到'自下而上'？ – Cratylus 2012-03-18 10:02:16

既然你要求參考，你應該去wikipedia,geekviewpoint和topcoder這樣的地方。

對於維基百科，您可以搜索「算法」。對於其他鏈接，只需遵循它們。

來源

2012-03-18 16:15:36 kasavbere

自底向上和自上而下是與樹遍歷不相關但與信息處理直接相關的術語。

自下而上的策略是一種綜合：你從理解的觀察中獲得信息。例如，您首先了解計算機程序，先理解彼此相近的語句，併合成子程序或程序的含義。你走得更遠，將程序的意義綜合到更大的部分，並最終你理解程序。另一個例子是語音識別，其中傳感器信息首先被合成爲音節，......詞語和含義，......句子和語句。

自上而下是分解的分析策略。例如，您可以在較小的部分分解問題，這些問題更易於處理。

來源

2012-03-20 10:24:46 Stefan

樹上的算法。有幫助指出有效解決方法的提示嗎？

回答

相關問題