二叉樹遍歷 三遍歷轉(zhuǎn)化詳解

《二叉樹遍歷 三遍歷轉(zhuǎn)化詳解》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、ABCDEFGHK如右圖，設(shè)有一棵二叉樹則它的三種遍歷分別為：先序遍歷：ABCDEFGHK中序遍歷：BDCAEHGKF后序遍歷：DCBHKGFEABCD左子樹（B）的三種遍歷：先序遍歷：BCD中序遍歷：BDC后續(xù)遍歷：DCBCD右子樹（C）的三種遍歷：先序遍歷：CD中序遍歷：DC后續(xù)遍歷：DCEFGHK對右子樹（E）進(jìn)行相同處理：先序遍歷：EFGHK中序遍歷：EHGKF后序遍歷：HKGFE...................................一直如此下去分析可得：先序遍歷的排列順序：根左子樹右子樹中序遍歷的排列順序：左子樹根右子樹后續(xù)遍歷的排列順序：左子樹右子樹根故采用

2、遞歸調(diào)用的方式可以較快得出遍歷算法：如知先序和中序求后序：Vars1,s2:String;Proceduretry(L1,r1,L2,r2:Integer);{當(dāng)前所求樹在先序序列中的起始、結(jié)束位置，在中序序列中的起始、結(jié)束位置}Varm:Integer;Beginm:=pos(s1[L1],s2);{求當(dāng)前樹的根節(jié)點(diǎn)在中序序列中的位置}Ifm>L2Thentry(L1+1,L1+m-L2,L2,m-1);{有左子樹，則處理左子樹，輸入左子樹在先序序列中的起始、結(jié)束位置，在中序序列中的起始、結(jié)束位置}Ifm

3、理右子樹，輸入右子樹在線序序列中的起始、結(jié)束位置，在中序序列中的起始、結(jié)束位置}Write(s1[L1]){輸出根結(jié)點(diǎn)}End;BeginReadln(s1);Readln(s2);try(1,Length(s1),1,Length(s2));Writeln;End.