根据二叉树的前序和中序序列输出后序序列

说在前面

这篇文章是对《新时代领航精品同步AB练数据与数据结构作业本》 “5.4递归算法的应用”第3题的一个勘误。并在此基础上对“根据二叉树的前序和中序序列输出后序序列”和“根据二叉树的后序和中序序列输出先序序列”两个问题进行深入探究，搞清楚递归函数的运行过程和算法原理。

原题展示

5.4 递归算法的应用练习A

3. 有如下递归函数：

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="")

调用语句fun("ABDECFG", "DBEAFCG", 7)后，程序输出的结果为（）

A. ABDECFG B. DBEAFCG C. DEFGBCA D. DEBFGCA

3. 解析：递归函数fun(a, b, n)的作用是根据二叉树的前序和中序序列输出后序序列，其中a和b分别表示存储了前序和中序序列的字符串,n表示字符串长度。程序用root表示中序序列b中根结点的下标，先在b中找到根结点下标，然后以root为界，将序列分成左右子树，再分别递归处理左右子树，最后输出根结点的值，由此可以输出二叉树的后序序列。

答案：D

跟踪程序运行过程

单看题目本身，程序没有问题，因为题目提供的二叉树的前序和中序序列字符串表明它是一棵满二叉树，任意时刻左右子树的长度均相等，故程序可以正常运行。

但是，当二叉树为非满二叉树时，函数fun(a, b, n)就要出错了，因为可能出现左右子树长度不等的情况。例如调用语句fun("ABDECF","DBEAFC", 6)时，会出现下标越界的错误。跟踪程序运行过程如下：

为了使程序正常运行，在递归输出左、右子树时，若左子树长度为root，则右子树长度应该为n-1-root。参考代码如下：

#根据二叉树的前序和中序序列输出后序序列def qz_h(a, b, n): if n > 0:root = 0while a[0] != b[root]: #在中序序列中查找根节点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="")   #输出根节点#主函数部分qz_h("ABDECFG","DBEAFCG", 7)

代码比较

都是输出后序序列，我们可以将“递归遍历一维数组输出后序序列”和“根据二叉树的前序和中序序列输出后序序列”两个函数的代码结构作比较：

可以看出二者的代码结构几乎完全一致，都是由递归出口和递归体组成，递归体中代码的执行顺序都是先输出左子树，再输出右子树，最后输出根节点。

区别有两处：

一是函数参数不同。postorder(array,i)函数中array是存储了完全二叉树的数组，i是当前根节点在数组array中的下标；qz_h(a, b, n) 函数中a和b分别是存储了二叉树前序和中序序列的字符串，n是字符串的长度。

二是postorder(array, i)函数直接给定了当前根节点下标，但是qz_h(a, b, n) 函数需要先在中序序列中找到根节点，再去输出左、右子树。

参考代码如下：

代码说明：我们使用变量root来指向根节点在字符串（或列表）b中的下标，因为根节点的值为a[0]，所以可以使用while循环语句到b中去寻找与a[0]相等的元素，b[root]即为根节点。

找到根节点的下标root后，易知左子树的前序序列为a[1:root+1]，中序序列为b[:root]，序列长度为root；右子树的前序序列为a[root+1:]，中序序列为b[root+1:]，序列长度为n-1-root。递归调用函数qz_h()，代入实参，即可实现递归输出左、右子树功能。

课后练习

除了“输出后序序列”，我们也可以“输出前序序列”。下面给出“递归遍历一维数组输出前序序列”和“根据二叉树的后序和中序序列输出前序序列”两个函数的代码结构，请你根据代码注释，填充相关代码，实现程序功能。

需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。