文件名称：采用数学归纳法证明。-数据结构报告
文件大小：607KB
文件格式：PPT
更新时间：2024-05-12 13:23:28
报告
采用数学归纳法证明。 当n=0时,二叉树为空,结论正确。 假设结点数小于n的任何二叉树,都可以由其先序序列和中序序列惟一地确定。 已知某棵二叉树具有n(n＞0)个不同结点,其先序序列是a0a1…an-1；中序序列是b0b1…bk-1bkbk+1…bn-1。 因为在先序遍历过程中,访问根结点后,紧跟着遍历左子树,最后再遍历右子树。所以,a0必定是二叉树的根结点,而且a0必然在中序序列中出现。也就是说,在中序序列中必有某个bk(0≤k≤n-1)就是根结点a0。