現實世界前/後階遍歷樹遍歷的例子

我很理解預訂，有序和後階遍歷算法。（Reference）。我理解了一些用途：按順序遍歷二叉搜索樹，按順序克隆樹。但是我不能爲了我的生活而想出一個真正的世界任務，我需要通過後序遍歷來完成。現實世界前/後階遍歷樹遍歷的例子

你能舉個例子嗎？而且：你能給我預訂遍歷的更好用法嗎？

編輯：任何人都可以給我一個例子，而不是表達式樹和RPN？那真的是所有的後期訂單都適合嗎？

來源

2010-08-20 Plutor

優秀的問題！ – Lazer 2010-08-20 22:30:48

Topological sorting是樹木（或向無環圖）一個後序遍歷。

這個想法是，圖的節點表示任務，從A到B的邊表示A必須在B之前執行。拓撲排序會按順序排列這些任務，以使任務的所有依賴關係都比任務本身早出現。任何構建系統如UNIX make必須實現此算法。

Dario提到的例子 - 使用手動內存管理銷燬樹的所有節點 - 就是這個問題的一個實例。畢竟，摧毀一個節點的任務取決於其子女的破壞。

來源

2010-08-21 08:54:04

這是一個很好的答案。記住樹是退化的圖可以打開各種功能。拓撲排序非常有用。 – Plutor 2010-08-23 13:57:54

爲什麼它被稱爲拓撲排序而不是計劃或什麼，或者什麼是「拓撲」在這種情況下應該表示的意思？ – Shawn 2011-04-30 03:08:04

@Shawn：打我。這可能是因爲只有圖形/網絡的拓撲很重要。 – 2011-05-03 18:12:18

郵政編碼是（可以）由編譯器使用。考慮一個a + b + c的表達式樹，機器語言將需要一個像a b + c +這樣的序列。這也被稱爲Reverse polish Notation（RPN）。在維基百科頁面上，它說：「RPN又名後綴」

銷燬樹也需要後期訂單，就像創建/克隆它需要預訂。

來源

2010-08-20 15:47:09

摧毀一棵樹，這是一個很好的觀點。 – Plutor 2010-08-20 16:08:21

+1它就像你可以使用預定順序克隆一棵樹，並使用反向步驟銷燬它，例如後序。應該有一些其他領域的前/後命令將非常有效。 – Lazer 2010-08-20 22:38:05

正如Henk Holterman指出的那樣，使用手動內存管理銷燬樹通常是後序遍歷。

僞代碼：

destroy(node) { 
    if (node == null) return; 

    destroy(node.left) 
    destroy(node.right) 

    // Post-order freeing of current node 
    free(node) 
}

來源

2010-08-20 16:09:28 Dario

現實世界前/後階遍歷樹遍歷的例子

回答

相關問題