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