編寫一個程序，實現(xiàn)二叉樹的先序遍歷，中序遍歷，后序遍歷的各種遞歸和非遞歸算法，以及層次遍歷的算法？二叉樹可以通過后序和中序遍歷進行恢復，以方便其他樹的操作。在這里，我們先恢復二叉樹，然后進行預序遍歷，

編寫一個程序，實現(xiàn)二叉樹的先序遍歷，中序遍歷，后序遍歷的各種遞歸和非遞歸算法，以及層次遍歷的算法？

二叉樹可以通過后序和中序遍歷進行恢復，以方便其他樹的操作。在這里，我們先恢復二叉樹，然后進行預序遍歷，得到預序遍歷的結(jié)果。我們同意恢復樹的函數(shù)稱為restoretree（）?；謴妥笥易訕鋾r，需要計算它們的位置，即H1、H2和Z1、Z2的值需要重新計算，并在更新后傳遞給restoretree（）函數(shù)。以左子樹的構(gòu)造為例，左子樹的第一個元素下標為Z1，最后一個元素下標為I-1，H1的對應值為H1，H2的值為H1（I-Z1-1），即H1的當前位置向前移動I-Z1-1長度。R代碼實現(xiàn)以實現(xiàn)前面提到的字母序列為例，因為當代碼恢復樹時，它首先恢復根節(jié)點，然后訪問樹的左、右子樹，所以恢復過程也相當于根優(yōu)先遍歷過程。如果只想先遍歷找到根，就不能構(gòu)建樹。我們可以刪除根優(yōu)先遍歷函數(shù)并簡化其他一些語句，這兩段代碼的結(jié)果是相同的。以下是示例輸入和輸出。這里的代碼擴展添加了一段代碼，它使用前序遍歷和中序遍歷來恢復二叉樹并進行后序遍歷。R代碼可以像以前一樣簡化。簡化后，無需建樹即可遍歷。這很正常。有必要多花點時間。首先需要了解堆棧的操作和意義，還需要了解遍歷二叉樹的思想。有人用節(jié)點著色來編寫非遞歸算法，即黑、灰、白三種顏色代表節(jié)點的狀態(tài)，未被訪問的節(jié)點為白色，未被訪問的節(jié)點為灰色，被訪問的節(jié)點為黑色。對于中間順序遍歷，除非訪問了左子樹，否則需要訪問當前節(jié)點，所以依次沿左子樹搜索，找到葉子后訪問，然后退出右堆棧上的元素，并在右子樹上執(zhí)行相應的操作，直到堆棧為空。