试证明：已知二叉树的前序序列和中序序列，可以唯一确定该二叉树

article/2025/6/24 3:01:10

假设二叉树BT的总的结点个数为n，前序序列pre为 $q_{1},q_{2},q_{3},...,q_{n}$ ，中序序列pin为 $z_{1},z_{2},z_{3},...,z_{n}$ ，现用数学归纳法证明pre和pin可以唯一确定这棵二叉树：

1. n = 1时，前序和中序序列都各只有一个元素 $q_{1}$ ， $z_{1}$ ，此时 $q_{1}$ 等于 $z_{1}$ ，为BT的根结点，唯一确定BT。

2. 假设 $n<m-1$ 时，pre和in可唯一确定二叉树BT，现证明当 $n=m$ 时，命题也能得证：

$n=m$ 时， $q_{1}$ 为二叉树的根结点，设 $q_{1}$ 在pin中对应的元素为 $z_{k}$ ，所以 $q_{1}$ 的左子树在pin中为 $z_{1},z_{2},z_{3},...,z_{k-1}$ ，在pre中为 $q_{2},q_{2},q_{3},...,q_{k}$ ； $q_{1}$ 的右子树在pin中为 $z_{k+1},z_{k+2},z_{k+3},...,z_{m}$ ，在pre中为 $q_{k+1},q_{k+2},q_{k+3},...,q_{m}$ 。

若 $k=1$ ，则 $q_{1}$ 没有左子树， $q_{1}$ 的右子树在pin中为 $z_{2},z_{3},z_{4},...,z_{m}$ ，在pre中为 $q_{2},q_{3},q_{4},...,q_{m}$ 。右子树结点的个数为 $m-2$ 由假设可知， $m-2<m-1$ ，所以 $q_{1}$ 的右子树可由pre和pin唯一确定。

若 $k=m$ ，则 $q_{1}$ 没有右子树， $q_{1}$ 的左子树在pin中为 $z_{1},z_{2},z_{3},...,z_{m-1}$ ，在pre中为 $q_{2},q_{2},q_{3},...,q_{m}$ 。左子树结点的个数为 $m-2$ ，由假设可知， $m-2<m-1$ ，所以 $q_{1}$ 的左子树可由pre和pin唯一确定。