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