实习二唯一的确定一颗二叉树.pdf

实习二 1.需求分析： 【问题描述】：如果给出了遍历二叉树的前序序列和中序序 列，则可以构造出唯一的二叉树。试编写实现上述功能的程 序。 【基本要求】： 已知一颗二叉树的前序和中序序列，试设计 完成下列任务的一个算法。 （1）构造一颗二叉树。 （2 ）证明构造正确（即分别以前序和中序遍历该树，将得 到的结果与给出的序列进行比较） 。 （3 ）对该二叉树进行后序遍历，输出后续遍历序列。 （4 ）用凹入法输出该二叉树。 【开发环境】： 系统： windows7 编程软件： VC++6.0 2.设计： 给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第 一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设 l个元素）表示左子树， 若左边无元素，则说明左子树为空；右边（设 r个元素）是右子树，若为空，则右子树为空。 根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的 l 个结点序列和中 序序列根左边的 l个结点构成左子树， 由前序序列最后 r个元素序列与中序序列根右边的 r个元 素序列构造右子树。 1 2 3 n 假设一棵二叉树中结点的个数为 n, 即该棵二叉树的前序遍历序列为 q , q , q , ?, q , 中序 遍历序列为 z 1, z 2 , z 3 , ?, z n , 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树 B t . 当 = 1 时 , 即前序遍历序列和中序遍历序列均只有一个元素 , 且相同 , 即为树的根 , 由此唯 n 一地确定了一棵二叉树。现在假设 n m - 1 时命题成立 , 则需要证明当 n= m 时亦成立。当 n= 1 2 3 m 1 2 3 m m 时 , 前序序列为 q , q , q , ?, q , 中序序列为 z , z , z , ?, z . 因为前序序列由前序遍历二叉树 1 所得 , 则 q 必为根结点这个元素 ; 又中序序列由中序遍历二叉树所得 , 则在中序序列中必能 1 j 1 2 j - 1 j + 1 j + 2 m 找到和 q 相同的元素 , 设为 z , 由此 { z , z , ?, z } 为左子树的中序序列 , { z , z , ?, z } 为 右子树的中序序列。若 j = 1, 即z 1 为根 , 此时二叉树的左子树为空 , {q2, q3, ?, qm } 为左子树的前 2 3 m 序序列 , { z , z , ?, z } 为右子树的中序序列。右子树的结点数为 m - 1, 根据假设 , 这两个序列 唯一确定了一棵右子树。因此 ,唯一确定的一棵二叉树是由 z 1 为根 , 该棵右子树为右子树