试题详情
简答题证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。
  • 证明采用归纳法。
    设二叉树的前序遍历序列为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唯一确定了根结点的右子树。

  • 关注下方微信公众号，在线模考后查看

热门试题