計算機二級公共基礎(chǔ)專題探究——二叉樹-文庫吧在線文庫
【正文】 RD 待求 由此可知，L=0，DR= ABCDEFGH 故RD=HGFEDCBA，即后序序列= HGFEDCBA變式訓(xùn)練1：已知后序序列與中序序列均為ABCDEFGH，求前序序列答案：HGFEDCBA，（這次R=0）結(jié)論：若前序序列與中序序列均為某序列，則后序序列為該序列的倒序，且為折線；同樣地，若后序序列與中序序列均為某序列，則前序序列為該序列的倒序，且為折線例2：已知前序序列=ABCD，中序序列=DCBA，求后序序列【解析】設(shè)根節(jié)點為D≠0，左子樹為L，右子樹為R，有遍歷順序為：前：DLR 已知ABCD 中：LDR 已知DCBA 后：LRD 待求因為ABCD與DCBA正好相反，由此可知，R=0所以DL=ABCD，即LD=DCBA所以后序序列= DCBA變式訓(xùn)練21：中序序列=BDCA，后序序列=DCBA，求前序序列【解析】設(shè)根節(jié)點為D≠0，左子樹為L，右子樹為R，有遍歷順序為：前：DLR 待求 中：LDR 已知BDC,A 后：LRD 已知DCB,A 通過觀察可知，R=0，L={B,D,C}，D=A中、后變換時，{B,D,C}發(fā)生了變化，說明左子樹結(jié)構(gòu)特殊，進一步令 中’：L’D’R’ 已知B,DC 后’：L’R’D’ 已知DC,B 可知L’=0，即D’=B，R’= DCA可以畫出二叉樹示意圖為：BCD所以前序序列= ABCD變式訓(xùn)練22：中序序列=ABC，后序序列=CBA，求前序序列【解析】設(shè)根節(jié)點為D≠0，左子樹為L，右子樹為R，有遍歷順序為：前：DLR 待求 中：LDR 已知ABC 后：LRD 已知通過觀察可知，L=0，DR=ABC，RD=CBA 所以前序序列=DLR= DR=ABC變式訓(xùn)練23：前序序列=ABC，中序序列=CBA，求后序序列【解析】設(shè)根節(jié)點為D≠0，左子樹為L，右子樹為R，有遍歷順序為：前：DLR 已知A,BC 中：LDR 已知CB,A 后
高考資料相關(guān)推薦
鄂ICP備17016276號-1