数据结构 第七章 二叉树确定的证明.doc

二叉树的确定 ? 1已知先序序列和中序序列可以确定唯一一棵二叉树 证明: (1) 如果先序遍历和中序遍历都是空或则只有一个结点易知该二叉树是唯一的 (2) 其它的情况 设少于n (n 2)个结点的二叉树可由先序遍历序列和中序遍历序列唯一确定 则对于有n 个结点的二叉树先序遍序历列中的第一个结点必然是该二叉树的根结点 然后在中序遍历序中找到根结点 故根结点可以唯一确定 在中序遍列序列中根结点前面的结