如何证明可以通过先序和中序，或者中序和后序确定唯一一个二叉树
证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树证明：由二叉树的后序序列和中序序列能唯一确定一棵二叉树 我们可以通过归纳法来证明由先序序列和中序序列，或后序序列和中序序列可以唯一确定一棵二叉树。这里我们分别证明这两个结论。
1、由二叉树的先序序列和中序序列能唯一确定一棵二叉树：
证明：
我们可以用归纳法证明这个结论。先看基本情况，当二叉树为空时，先序序列和中序序列都为空，满足唯一性。
现在假设所有节点数小于等于k的二叉树都满足这个结论，我们需要证明当节点数为k+1时，结论依然成立。
设二叉树有k+1个节点，先序序列为{A1, A2, ... , Ak+1}，中序序列为{B1, B2, ... , Bk+1}。我们知道先序序列的第一个节点A1是根节点，通过中序序列我们可以找到A1在中序序列中的位置，设为i。则A1左子树的节点在中序序列中的位置是{B1, B2, ... , Bi-1}，右子树的节点在中序序列中的位置是{Bi+1, ... , Bk+1}。
由于左子树的节点数目小于等于k，根据归纳假设，左子树可以由先序序列的{A2, ... , A_i}和中序序列的{B1, ... , Bi-1}唯一确定。同样，右子树也可以由先序序列的{A_i+1, ... , Ak+1}和中序序列的{Bi+1, ... , Bk+1}唯一确定。
所以当节点数为k+1时，先序序列和中序序列可以唯一确定一棵二叉树，结论得证。
2、由二叉树的后序序列和中序序列能唯一确定一棵二叉树：
证明：
同样地，我们使用归纳法证明。首先，当二叉树为空时，后序序列和中序序列都为空，满足唯一性。
现在假设所有节点数小于等于k的二叉树都满足这个结论，我们需要证明当节点数为k+1时，结论依然成立。
设二叉树有k+1个节点，后序序列为{A1, A2, ... , Ak+1}，中序序列为{B1, B2, ... , Bk+1}。我们知道后序序列的最后一个节点Ak+1是根节点，通过中序序列我们可以找到Ak+1在中序序列中的位置，设为i。则Ak+1左子树的节点在中序序列中的位置是{B1, B2, ... ,Bi-1}，右子树的节点在中序序列中的位置是{Bi+1, ... , Bk+1}。
由于左子树的节点数目小于等于k，根据归纳假设，左子树可以由后序序列的{A1, ... , A_i-1}和中序序列的{B1, ... , Bi-1}唯一确定。同样，右子树也可以由后序序列的{A_i, ... , Ak}和中序序列的{Bi+1, ... , Bk+1}唯一确定。
所以当节点数为k+1时，后序序列和中序序列可以唯一确定一棵二叉树，结论得证。
综上，我们证明了由二叉树的先序序列和中序序列能唯一确定一棵二叉树，以及由二叉树的后序序列和中序序列能唯一确定一棵二叉树。
页:
[1]