怎样由遍历序列确定二叉树.pdf

维普资讯 洛阳师范学院学报 2003年第 2期 怎 样 由 遍 历 序 列 确 定 二 叉 树 康 牧，陈向奎 (洛阳师范学院计算机系，河南洛阳471022) 摘 要-在文[1]至文[4]中都介绍了遍历一棵二又树的三种方法：先序遍历、中序遍历和后 序遍历 ．每棵二又树的先序遍历序列、中序遍历序列和后序遍 历序 列都是唯一的、但 是不同 的二又树的先序遍历序列或 中序遍历序列或后序遍历序列有可能是相 同的．就如我们 已知一 个关系要求能求 出它的关系矩 阵，已知一个关系的关系矩阵也能求 出关系矩 阵所表示的关系 一 样 ，要求我们不但能从二又树求它的遍序序列，而且能从二叉树 的遍历序列求出它们所表 示的二又树 ．在文[1]中只指出：给定结点的先序序列和 中序序列可唯一确定一棵二叉树 ．但 文[1]没有给出证 明．本文指出了由后序遍历序列和 中序遍历序列也可唯一确定一棵二叉树， 并给 出了相应 的证 明， 关键词-二叉树 ；先序遍 历；中序遍历；后序遍历 ；位置树 中图分类号：TP3I】．12 文献标识码 ：A 文章编号 ：1009—4970(2003)02—0056—03 因为不同的二叉树可以有相 同的先序遍历序列或中序遍历序列或后序遍历序列 ，但三种遍历序列 不可能都相同，故我们可以由不同的遍历序列相结合来唯一确定一棵二叉树 ． 文[1]一[4]都给 出了二叉树 的三处遍历方法 的递归算法 ，文[1]和文 [2]还给 出了相应的程序实 现 ． 1 先序遍历序列和中序遍历序列可 以唯一确定一棵二叉树 证 明-(1)如果先序遍历序列和中序遍历序列都是空，则该二叉树是空树 ，而空二叉树是唯一的． (2)如果先序遍历序列和 中序遍历序列 中都只有一个结点，那么该二叉树是只有一个结点 二叉树 ，而只有一个结点的二叉树也是唯一的． (3)其它的情况 ，设少于n(n≥2)个结点的二又树可由先序遍历序列和中序遍历序列唯一确 定 ．则对于有 n个结点的二叉树，先序遍序历列中的第一个结点必然是该 二叉树的根结点，然后在 中 序遍历序中找到根结点，故根结点可以唯一确定．在中序遍列序列 中根结点前面的结点序列就是根结 点左子树的中序遍历序列 ，在先序遍历序列中根结点后面的属于中序遍历序列中根结点前面的那些结 点组成序列就是根结点左子树的先序遍历序列 ，因为根结点的左子树至少比原二叉树少一个结点，所 以根据归纳假设可知根结点的左子树是唯一的：原中序序列中根结点后面的结点序列就是根结点右子 树的中序序列 ，原先序序列 中去掉左子树先序序列后剩下的结点序列就是根结点右子树的先序序列， 根结点的右子树至少比原二叉树少一个结点，根据归纳假设可知根结点的右子树也是唯一的．所以对 于有 n个结点的二叉树也可由先序遍历序列和中序遍历序列唯一确定 ． 由(1)、(2)、(3)可知对于任意个结点的二叉树都可由先序遍历序列和中序遍历序列唯一确定 ． 2 后序遍历序列和中序遍历序列也可唯一确定一棵二叉树 证明-(1)如果后序遍历序列和中序遍历序列都是空，则该二叉树是空树 ，而空二叉树是唯一的． (2)如果后序遍历序列和 中序遍历序列中都只有一个结点，那么该二叉树是只有一个结点 二叉树 ，而只有一个结点的二叉树也是唯一的． 收稿 日期 ：2OO2—08—2l 作者简介：康 牧(1968一)，男，河南伊川人，讲师． 维普资讯 洛阳师范学院学报 2003年第 2期 ·57 · (3)其它情况 ，设少于 n(n≥0)个结点的二叉树可 由后序遍历序列和 中序遍历序列唯一确 定 ．则对于有 n个结点的二叉树，后序遍历序列中的最后一个结点必然是该二叉树的根结点．然后在 中序遍历序列中找到根结点，故根结点可以唯一确定，在中序遍历序列中根结点后面的结点序列就是 根结点右子树的中序遍历序列 ，在后序