唯一的确定一棵二叉树(共12页).doc

精选优质文档-倾情为你奉上数据结构课程设计唯一的确定一棵二叉树 n 指导教师:n 设计人: n 班级： n 学号： 设计时间：2011年4月18实习二 树、图及其应用题目：唯一的确定一棵二叉树实习时间：2011.4.15一、需求分析：1. 如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。已知一棵二叉树的前序和中序序列，设计完成下列任务的一个算法：（1）构造一棵二叉树；（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。2.测试数据：前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。二、设计：n 设计思想（1）存储结构:二叉树 ，用两个一维数组A和B分别存放前序和中序序列。（2）主要算法基本思想：将前序和中序序列分别读入数组A和B。根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。