求数据结构题集6.32题证明全过程。解决思路
求数据结构题集6.32题证明全过程。
这是数据结构题集6.32题：证明：如果一棵二叉树的先序序列是u1,u2,....,un,中序序列是up1,up2...,upn,则序列1,2,...,n可以通过一个栈得到序列p1,p2,...,pn；反之，若以上述中的结论作为前提，则存在一棵二叉树，若前序序列是u1,u2,...un,则其中序序列为up1,up2....upn.
请给出详细的第二归纳法证明全过程（严谨的全过程，而不是简单解析）
可以另外加分，谢谢。
------解决方案--------------------
很基础的数学归纳法：
对第一问：
当n=1时结论显然成立
假设结论对所有<n的数都成立，n>1，用第二归纳法证明结论对n也成立：
首先，u1是这颗数的根，设p_i=1, 那么p_1,...,p_(i-1)是这棵树的左子树中序遍历，2,...,i是其左子树的前序遍历。同理，p_(1+1),...,p_n是这棵树右子树的中序遍历，i+1,...,n是右子树的前序遍历。先把1入栈，然后根据归纳假设，p_1,...,p_(i-1)可以利用栈由2,...,i得到，然后把1出栈(因为1就是p_i)，又根据归纳假设，p_(1+1),...,p_n可以由i+1,...,n利用栈得到。完毕。
对第二问也是类似：
前面同上，省略，证明对n成立：
即已知序列1,...,n可以利用栈得到p_1,...,p_n, 假设p_i=1, 由栈的工作原理知，p_1,...,p_(i-1)可以利用栈由2,...,i得到，由归纳假设，存在一颗树T1, 使得2,...,i是前序遍历，p_1,...,p_(i-1)是中序遍历. 同样，存在T2，使得i+1,...,n是前序遍历，p_i,...,p_n是中序遍历。把1作为根，T1，T2分别作为左右子树，这样出来的树就满足条件。完毕。
这是数据结构题集6.32题：证明：如果一棵二叉树的先序序列是u1,u2,....,un,中序序列是up1,up2...,upn,则序列1,2,...,n可以通过一个栈得到序列p1,p2,...,pn；反之，若以上述中的结论作为前提，则存在一棵二叉树，若前序序列是u1,u2,...un,则其中序序列为up1,up2....upn.
请给出详细的第二归纳法证明全过程（严谨的全过程，而不是简单解析）
可以另外加分，谢谢。
------解决方案--------------------
很基础的数学归纳法：
对第一问：
当n=1时结论显然成立
假设结论对所有<n的数都成立，n>1，用第二归纳法证明结论对n也成立：
首先，u1是这颗数的根，设p_i=1, 那么p_1,...,p_(i-1)是这棵树的左子树中序遍历，2,...,i是其左子树的前序遍历。同理，p_(1+1),...,p_n是这棵树右子树的中序遍历，i+1,...,n是右子树的前序遍历。先把1入栈，然后根据归纳假设，p_1,...,p_(i-1)可以利用栈由2,...,i得到，然后把1出栈(因为1就是p_i)，又根据归纳假设，p_(1+1),...,p_n可以由i+1,...,n利用栈得到。完毕。
对第二问也是类似：
前面同上，省略，证明对n成立：
即已知序列1,...,n可以利用栈得到p_1,...,p_n, 假设p_i=1, 由栈的工作原理知，p_1,...,p_(i-1)可以利用栈由2,...,i得到，由归纳假设，存在一颗树T1, 使得2,...,i是前序遍历，p_1,...,p_(i-1)是中序遍历. 同样，存在T2，使得i+1,...,n是前序遍历，p_i,...,p_n是中序遍历。把1作为根，T1，T2分别作为左右子树，这样出来的树就满足条件。完毕。