证明采用归纳法。
设二叉树的前序遍历序列为a1a2a3…an，中序遍历序列为b1b2b3…bn。
当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1=b1，可以唯一确定该二叉树；
假设当n<=k时，前序遍历序列a1a2a3…ak和中序遍历序列b1b2b3…bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3…akak+1和中序遍历序列b1b2b3…bkbk+1可唯一确定一棵二叉树。
在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2…bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3…ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3…ai和中序遍历序列b1b2…bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2…ak+1和中序遍历序列bi+1bi+2…bk+1唯一确定了根结点的右子树。
（简答题）
证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。
正确答案
答案解析
略
相似试题
（判断题）
已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。
（判断题）
已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。
（判断题）
若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树
（单选题）
任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。
（判断题）
由一棵二叉树的前序序列和后序序列可以唯一确定它。
（单选题）
任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（）。
（简答题）
已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。
（单选题）
一棵二叉树的前（先）序序列为ABCDEFG，则它的中序序列不可能为（）。
（判断题）
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系都相同。
