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

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

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