求一個二叉樹的后序遍歷非遞歸算法？此主題為p=t while（1）{if（p->rchild）//如果有右子級，則右子級必須在序列中的當(dāng)前節(jié)點之后（如果有另一個左子級，則右子級也在整個左子樹之后）

求一個二叉樹的后序遍歷非遞歸算法？

此主題為p=t while（1）{if（p->rchild）//如果有右子級，則右子級必須在序列中的當(dāng)前節(jié)點之后（如果有另一個左子級，則右子級也在整個左子樹之后）p=p->rchild else if（p->lchild）//如果沒有右子級，但有左子級，左子級必須在序列P=P->lchild Else//last break}return P中的當(dāng)前節(jié)點之后

使用后序和中序遍歷來還原二叉樹。后序和中序遍歷可以恢復(fù)二叉樹，方便其他樹的操作。在這里，我們先恢復(fù)二叉樹，然后進行預(yù)序遍歷，得到預(yù)序遍歷的結(jié)果。我們同意恢復(fù)樹的函數(shù)稱為restoretree（）。恢復(fù)左右子樹時，需要計算它們的位置，即H1、H2和Z1、Z2的值需要重新計算，并在更新后傳遞給restoretree（）函數(shù)。以左子樹的構(gòu)造為例，左子樹的第一個元素下標為Z1，最后一個元素下標為I-1，H1的對應(yīng)值為H1，H2的值為H1（I-Z1-1），即H1的當(dāng)前位置向前移動I-Z1-1長度。R代碼實現(xiàn)以實現(xiàn)前面提到的字母序列為例，因為當(dāng)代碼恢復(fù)樹時，它首先恢復(fù)根節(jié)點，然后訪問樹的左、右子樹，所以恢復(fù)過程也相當(dāng)于根優(yōu)先遍歷過程。如果只想先遍歷找到根，就不能構(gòu)建樹。我們可以刪除根優(yōu)先遍歷函數(shù)并簡化其他一些語句，這兩段代碼的結(jié)果是相同的。以下是示例輸入和輸出。這里的代碼擴展添加了一段代碼，它使用前序遍歷和中序遍歷來恢復(fù)二叉樹并進行后序遍歷。R代碼可以像以前一樣簡化。簡化后，無需建樹即可遍歷。右