根據(jù)二叉樹的前序和中序序列輸出后序序列
說在前面
這篇文章是對(duì)《新時(shí)代領(lǐng)航精品同步AB練 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu) 作業(yè)本》 “5.4遞歸算法的應(yīng)用”第3題的一個(gè)勘誤。并在此基礎(chǔ)上對(duì)“根據(jù)二叉樹的前序和中序序列輸出后序序列”和“根據(jù)二叉樹的后序和中序序列輸出先序序列”兩個(gè)問題進(jìn)行深入探究，搞清楚遞歸函數(shù)的運(yùn)行過程和算法原理。
5.4 遞歸算法的應(yīng)用 練習(xí)A
3. 有如下遞歸函數(shù)：
def fun(a, b, n): ?
???if n > 0:
???????root = 0
???????while a[0] != b[root]: ?
???????????root += 1
???????fun(a[1:root+1], b[:root], root)
???????fun(a[root+1:], b[root+1:], root) ?
???????print(a[0], end="")
調(diào)用語(yǔ)句fun("ABDECFG", "DBEAFCG", 7)后，程序輸出的結(jié)果為（ ???）
A. ABDECFG????? B. DBEAFCG????? C. DEFGBCA????? D. DEBFGCA
3. 解析：遞歸函數(shù)fun(a, b, n)的作用是根據(jù)二叉樹的前序和中序序列輸出后序序列，其中a和b分別表示存儲(chǔ)了前序和中序序列的字符串,n表示字符串長(zhǎng)度。程序用root表示中序序列b中根結(jié)點(diǎn)的下標(biāo)，先在b中找到根結(jié)點(diǎn)下標(biāo)，然后以root為界，將序列分成左右子樹，再分別遞歸處理左右子樹，最后輸出根結(jié)點(diǎn)的值，由此可以輸出二叉樹的后序序列。
答案：D
跟蹤程序運(yùn)行過程
單看題目本身，程序沒有問題，因?yàn)轭}目提供的二叉樹的前序和中序序列字符串表明它是一棵滿二叉樹，任意時(shí)刻左右子樹的長(zhǎng)度均相等，故程序可以正常運(yùn)行。
但是，當(dāng)二叉樹為非滿二叉樹時(shí)，函數(shù)fun(a, b, n)就要出錯(cuò)了，因?yàn)榭赡艹霈F(xiàn)左右子樹長(zhǎng)度不等的情況。例如調(diào)用語(yǔ)句fun("ABDECF","DBEAFC", 6)時(shí)，會(huì)出現(xiàn)下標(biāo)越界的錯(cuò)誤。跟蹤程序運(yùn)行過程如下：
為了使程序正常運(yùn)行，在遞歸輸出左、右子樹時(shí)，若左子樹長(zhǎng)度為root，則右子樹長(zhǎng)度應(yīng)該為n-1-root。參考代碼如下：
#根據(jù)二叉樹的前序和中序序列輸出后序序列def qz_h(a, b, n):if n > 0:root = 0while a[0] != b[root]: #在中序序列中查找根節(jié)點(diǎn)root += 1#輸出左子樹qz_h(a[1:root+1], b[:root], root)#輸出右子樹qz_h(a[root+1:], b[root+1:], n-1-root)print(a[0], end="") #輸出根節(jié)點(diǎn)#主函數(shù)部分qz_h("ABDECFG","DBEAFCG", 7)
代碼比較
都是輸出后序序列，我們可以將“遞歸遍歷一維數(shù)組輸出后序序列”和“根據(jù)二叉樹的前序和中序序列輸出后序序列”兩個(gè)函數(shù)的代碼結(jié)構(gòu)作比較：
可以看出二者的代碼結(jié)構(gòu)幾乎完全一致，都是由遞歸出口和遞歸體組成，遞歸體中代碼的執(zhí)行順序都是先輸出左子樹，再輸出右子樹，最后輸出根節(jié)點(diǎn)。
區(qū)別有兩處：
一是函數(shù)參數(shù)不同。postorder(array,i)函數(shù)中array是存儲(chǔ)了完全二叉樹的數(shù)組，i是當(dāng)前根節(jié)點(diǎn)在數(shù)組array中的下標(biāo)；qz_h(a, b, n) 函數(shù)中a和b分別是存儲(chǔ)了二叉樹前序和中序序列的字符串，n是字符串的長(zhǎng)度。
二是postorder(array, i)函數(shù)直接給定了當(dāng)前根節(jié)點(diǎn)下標(biāo)，但是qz_h(a, b, n) 函數(shù)需要先在中序序列中找到根節(jié)點(diǎn)，再去輸出左、右子樹。
參考代碼如下：
代碼說明：我們使用變量root來(lái)指向根節(jié)點(diǎn)在字符串（或列表）b中的下標(biāo)，因?yàn)楦?jié)點(diǎn)的值為a[0]，所以可以使用while循環(huán)語(yǔ)句到b中去尋找與a[0]相等的元素，b[root]即為根節(jié)點(diǎn)。
找到根節(jié)點(diǎn)的下標(biāo)root后，易知左子樹的前序序列為a[1:root+1]，中序序列為b[:root]，序列長(zhǎng)度為root；右子樹的前序序列為a[root+1:]，中序序列為b[root+1:]，序列長(zhǎng)度為n-1-root。遞歸調(diào)用函數(shù)qz_h()，代入實(shí)參，即可實(shí)現(xiàn)遞歸輸出左、右子樹功能。
課后練習(xí)
除了“輸出后序序列”，我們也可以“輸出前序序列”。下面給出“遞歸遍歷一維數(shù)組輸出前序序列”和“根據(jù)二叉樹的后序和中序序列輸出前序序列”兩個(gè)函數(shù)的代碼結(jié)構(gòu)，請(qǐng)你根據(jù)代碼注釋，填充相關(guān)代碼，實(shí)現(xiàn)程序功能。
需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來(lái)！
相關(guān)優(yōu)秀文章：