關(guān)于二叉樹 1、前中后序遍歷

在已知中序的前提下，任意知道前序或后序皆可得到唯一的二叉樹

創(chuàng)新互聯(lián)專注于薩爾圖網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供薩爾圖營銷型網(wǎng)站建設(shè)，薩爾圖網(wǎng)站制作、薩爾圖網(wǎng)頁設(shè)計、薩爾圖網(wǎng)站官網(wǎng)定制、微信小程序服務(wù)，打造薩爾圖網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供薩爾圖網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

假若一個中序序列為：ABEDFCHG

又知前序序列為：CBADEFGH

由于前序序列是按照根左右來進行遍歷的

所以前序序列的第一個一定是二叉樹的根結(jié)點！

即：

然后中序序列是按照左根右來進行遍歷的

所以中序序列的根一定將左右子樹進行了分離

先不管ABEDF哪個是根，反正他們都是作為C的左子樹的一個結(jié)點

HG則作為C的右子樹

即：

接下來前序序列的下一個又是一個子根，所以重復(fù)前面的操作得到：

接下來在中序中A的左右已經(jīng)沒有更后的結(jié)點了也就說明它沒有左右子樹(屬于葉子結(jié)點)

在中序中(ABEDFCHG), A的左邊沒有元素，A的右邊是B，但是B是在前面的，
所以B不會作為A的子樹，故A的左右都沒有元素，得出A是葉子結(jié)點的結(jié)論

最終成圖：

2、根據(jù)前中序來推后序序列

首先假若有一個中序序列為：ABEDFCHG

又知前序序列為：CBADEFGH

那么我們先分析后序遍歷的需求，后序是根據(jù)左右根來遍歷的

所以我們先要找根的左子樹結(jié)點，再根據(jù)左子樹結(jié)點找其左子樹結(jié)點，直到左子樹結(jié)點為空

然后再找返回去根節(jié)點找其右子樹，重復(fù)上述內(nèi)容(找右子樹的左子樹)

所以根據(jù)我們的分析得出，這個題可以使用遞歸來解決

遞歸思想：把規(guī)模大的、較難解決的問題變成規(guī)模小的、易解決的同一問題。規(guī)模較小的問題又變成規(guī)模更小的問題，并且小到一定程度可以直接得出它的解，從而得到原來問題的解。
三個使用條件：
1、可以將一個大問題轉(zhuǎn)為小問題
2、可以通過轉(zhuǎn)化過程使得問題得到解決
3、有一個明確的結(jié)束遞歸的條件

根據(jù)上圖我們可以寫出代碼

首先找出根節(jié)點(第一個根節(jié)點是C)

然后左子樹是：ABEDF，右子樹為HG

然后再根據(jù)左子樹中找到根節(jié)點B(通過中序的下一位來判斷)

我們可以每記錄了一次根節(jié)點之后可以將對應(yīng)的根節(jié)點清除，這樣后面就不用特別處理了
這里提供一種清除方法
清除前序遍歷的根節(jié)點：tpreor.erase(tpreor.begin());
清除中序遍歷的根節(jié)點：tinfor.erase(temp, 1);
( temp 為 tinfor.find(root) -->root為每一次的根節(jié)點 root = tpreor[0]);
又或者可以利用下標來進行操作，只不過使用清除的方法更加明顯實質(zhì)一點
利用下標的話就不用進行清除了，每次只需要改變下標即可

然后在遍歷左子樹來重復(fù)前面的操作

直到左子樹都執(zhí)行結(jié)束后再對右子樹進行同樣的操作

具體實現(xiàn)為：
traversal(left_tpreor, left_tinfor);
traversal(right_tpreor, right_tinfor);
若左右子樹都遍歷結(jié)束后再進行輸出根節(jié)點
cout<< root; //因為是后序遍歷(只有左子樹和右子樹到頭了再輸出根結(jié)點)

完整代碼：

#include#includeusing namespace std;

string preor, infor;
//前序后序 
void traversal(string tpreor, string tinfor){
	
	if(tinfor.empty()) return;	//這時候中序的元素都找完了，就可以返回程序了
	char root = tpreor[0]; //取根節(jié)點
	int temp = tinfor.find(root);	//從中序中找根結(jié)點
	tpreor.erase(tpreor.begin());	//清除前序最前面的字符
	tinfor.erase(temp, 1);	//清除中序的根結(jié)點
	string left_tpreor = tpreor.substr(0, temp);	//記錄左子樹
	string left_tinfor = tinfor.substr(0, temp);
	string right_tpreor = tpreor.substr(temp);	//記錄右子樹
	string right_tinfor = tinfor.substr(temp);
	
	traversal(left_tpreor, left_tinfor);	//操作左子樹
	traversal(right_tpreor, right_tinfor);	//操作右子樹
	cout<< root;	//左子樹和右子樹都遍歷完了后就可以輸出了
	
}

int main()
{
	
	cin >>infor >>preor;
	
	traversal(preor, infor);
	
	return 0;
}

未完待續(xù)…

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞標題：關(guān)于二叉樹-創(chuàng)新互聯(lián)
瀏覽地址：http://weahome.cn/article/dsdsji.html