[已解决]如何证明可以通过先序和中序，或者中序和后序确定唯一一个二叉树

白痴爱面包

证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树
证明：由二叉树的后序序列和中序序列能唯一确定一棵二叉树

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-16 20:55:56

我们可以通过归纳法来证明由先序序列和中序序列，或后序序列和中序序列可以唯一确定一棵二叉树。这里我们分别证明这两个结论。

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时，后序序列和中序序列可以唯一确定一棵二叉树，结论得证。

综上，我们证明了由二叉树的先序序列和中序序列能唯一确定一棵二叉树，以及由二叉树的后序序列和中序序列能唯一确定一棵二叉树。

跳转到最佳答案楼层

isdkz

我们可以通过归纳法来证明由先序序列和中序序列，或后序序列和中序序列可以唯一确定一棵二叉树。这里我们分别证明这两个结论。

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时，后序序列和中序序列可以唯一确定一棵二叉树，结论得证。

综上，我们证明了由二叉树的先序序列和中序序列能唯一确定一棵二叉树，以及由二叉树的后序序列和中序序列能唯一确定一棵二叉树。