资源描述：
《唯一的确定一棵二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构》课程设计唯一的确定一棵二叉树n指导教师:n设计人:n班级：n学号：设计时间：2011年4月18实习二树、图及其应用题目：唯一的确定一棵二叉树实习时间：2011.4.15一、需求分析：1.如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。已知一棵二叉树的前序和中序序列，设计完成下列任务的一个算法：（1）构造一棵二叉树；（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。2.测试数据：前序序列为ABDEGCFHIJ，中序序列
2、为DBGEAHFIJC。二、设计：n设计思想（1）存储结构:二叉树，用两个一维数组A和B分别存放前序和中序序列。（2）主要算法基本思想：①将前序和中序序列分别读入数组A和B。②根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。所以，首先从数组A中取出第一个元素A[0]作根结点，然后在数组B中找到A[0]，以它为界，在其前面的是左子树中序序列，在其后面的是右子树中序序列。③若左子树不为空，沿前序序列向后移动，找到左子树根结点，转②。④左子树构造完毕后，
3、若右子树不为空，沿前序序列向后移动，找到右子树根结点，转②。⑤前序序列中各元素取完则二叉树构造完毕。⑥对二叉树进行前序和中序遍历，并将结果分别与数组A和B进行比较，若相同，则证明二叉树构造正确。n设计表示（1）函数调用关系图：main→InitiateCreateTreePrintBiTreePreOrder→VisitInOrder→VisitPostOrder（2）函数接口规格说明：voidInitiate(BiTNode**root)//初始化二叉树的头结点voidVisit(charitem)//访问操
4、作voidPreOrder(BiTNode*T,voidVisit(charitem))//前序遍历二叉树voidInOrder(BiTNode*T,voidVisit(charitem))//中序遍历二叉树voidPostOrder(BiTNode*T,voidVisit(charitem))//后序遍历二叉树voidPrintBiTree(BiTNode*T,intn)//显示二叉树voidCreateTree(BiTNode*T,intpre_f,intpre_l,intin_f,intin_l,char
5、pre[],charin[])//按要求创建二叉树n实现注释（1）根据前序遍历和后序遍历创建二叉树，并后序遍历该二叉树。（2）二叉树逆转90度来显示。n详细设计总体来说，本程序设计相对比较简单，主要包括七个功能模块：初始化函数、前序遍历二叉树函数、中序遍历二叉树函数、后序遍历二叉树函数、显示函数、创建二叉树函数、主函数。下面分别给予介绍：Ø初始化函数voidInitiate(BiTNode**root){*root=(BiTNode*)malloc(sizeof(BiTNode));(*root)->LeftC
6、hild=NULL;(*root)->RightChild=NULL;}Ø前序遍历二叉树函数voidPreOrder(BiTNode*T,voidVisit(charitem)){if(T!=NULL){Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);}}Ø中序遍历二叉树函数voidInOrder(BiTNode*T,voidVisit(charitem)){if(T!=NULL){InOrder(T->Left
7、Child,Visit);Visit(T->data);InOrder(T->RightChild,Visit);}}Ø后序遍历二叉树函数voidPostOrder(BiTNode*T,voidVisit(charitem)){if(T!=NULL){PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);}}Ø显示函数voidPrintBiTree(BiTNode*T,intn){inti;if(T==NULL)r
8、eturn;PrintBiTree(T->RightChild,n+1);for(i=0;i=0){printf("_________________↗");printf("%c",T->data);}PrintBiTree(T->LeftChild,n+1);}Ø创建二叉树函数voidCreateTree(BiTNode*T,in
