唯一的确定一棵二叉树

1、课程设计唯一的确定一棵二叉树设计时间：2011 年 4 月 18树、图及其应用题目：唯一的确定一棵二叉树实习时间：2011.4.15一、需求分析：1. 如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。 试编写实现上述功能的程序。已知一棵二叉树的前序和中序序列，设计完成下列任务的一个算法：（ 1）构造一棵二叉树；（ 2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。2. 测试数据：前序序列为ABDEGCFH，中序序列为IJDBGEAHFIJ。 C二、设计：设计思想（ 1）存储结构: 二叉树 ，用两个一维数组A 和 B 分别存放前序和中序序列

2、。（ 2）主要算法基本思想：将前序和中序序列分别读入数组A和 B。根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。所以， 首先从数组A中取出第一个元素A0 作根结点，然后在数组B 中找到 A0 ，以它为界，在其前面的是左子树中序序列，在其后面的是右子树中序序列。若左子树不为空，沿前序序列向后移动，找到左子树根结点，转。左子树构造完毕后，若右子树不为空，沿前序序列向后移动，找到右子树根结点，转。前序序列中各元素取完则二叉树构造完毕。对二叉树进行前序和中序遍历，并将结果分别与数组A和 B进行比较，若相同，则证明二叉树构造正确。设计表示

3、（ 1）函数调用关系图： main InitiateCreateTree PrintBiTreePreOrder VisitInOrder Visit PostOrder( 2)函数接口规格说明：void Initiate(BiTNode *root)/ 初始化二叉树的头结点void Visit(char item)/ 访问操作void PreOrder(BiTNode *T,void Visit(char item)/前序遍历二叉树void InOrder(BiTNode *T,void Visit(char item)/中序遍历二叉树void PostOrder(BiTNode *T,vo

4、id Visit(char item)/后序遍历二叉树void PrintBiTree(BiTNode *T,int n)/ 显示二叉树void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char pre,char in)/ 按要求创建二叉树实现注释（ 1）根据前序遍历和后序遍历创建二叉树，并后序遍历该二叉树。（ 2）二叉树逆转90 度来显示。详细设计总体来说，本程序设计相对比较简单，主要包括七个功能模块：初始化函数、 前序遍历二叉树函数、中序遍历二叉树函数、后序遍历二叉树函数、显示函数、创建二叉树函数、主函数。下面

5、分别给予介绍：初始化函数void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)->LeftChild=NULL;(*root)->RightChild=NULL;前序遍历二叉树函数void PreOrder(BiTNode *T,void Visit(char item) if(T!=NULL)Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);中序遍历二叉树函数void I

6、nOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);后序遍历二叉树函数void PostOrder(BiTNode *T,void Visit(char item) if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);显示函数void PrintBi

7、Tree(BiTNode *T,int n)int i;if(T=NULL) return;PrintBiTree(T->RightChild,n+1);for(i=0;i<n;i+) printf(" ");if(n>=0)printf(" ");printf("%cnn",T->data);PrintBiTree(T->LeftChild,n+1);创建二叉树函数void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char

8、pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame)while(prepre_f!=insame)/ 在中序序列中找到根节点same+;interval+;if(interval=0)&&(pre_f=pre_l) / 找到了叶节点，也是递归出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同时存在左子树和右子树T->L

9、eftChild=(BiTNode *)malloc(sizeof(BiTNode);T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_f+interval,in_f,in_f+interval-1,p re,in);CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);if(interval!=0)&&

10、(interval=pre_l-pre_f)/只有左子树T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,pre,in); T->RightChild=NULL;if(interval=0)&&(pre_f!=pre_l)/ 只有右子树T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=pr

11、epre_f;T->LeftChild=NULL;CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);主函数void main()BiTNode *T;int Pre_len,In_len;char PreMaxSize;/ 前序序列char InMaxSize;/ 中序序列printf(" 请输入前序序列：n");scanf("%s",&Pre);Pre_len=strlen(Pre);printf(" 请输入中序序列：

12、n");scanf("%s",&In);In_len=strlen(In);Initiate(&T);CreateTree(T,0,Pre_len-1,0,In_len-1,Pre,In);printf(" 二叉树构造成功！n");printf("逆时针旋转90 度的二叉树如下所示：n");PrintBiTree(T,0);printf("前序序列：n");PreOrder(T,Visit);printf("n中序序列：n");InOrder(T,Visit);prin

13、tf("n后序序列：n");PostOrder(T,Visit);printf("n");三、调试分析：本程序在设计过程中遇到一个难题，那就是如何正确显示所构造的二叉树，试了几种方法都不理想，最后想到让二叉树逆时针旋转后再显示，具备可行性，同时也使之更美观。经验和体会经过第一次一元稀疏多项式加法的课程设计，这次课程设计就显得轻车熟路了，运算的主要设计思路很容易想到，大体设计结构在较短时间内能够完成，但当设计到具体细节代码时遇到了一些困难，主要困难是进行结点操作时，对指针考虑得不够细致，调试时常出现指针指错的情况，没有认真理清条件层次，另一个困难是如何正确

14、显示所构造的二叉树。虽然程序可能并不是最高效的，而且不够健壮，但也符合题目的要求，总的来说本次课程设计还算圆满。本次课程设计培养了我对实际问题的分析能力以及解决一些实际问题的能力， 巩固了我的编程思想和写程序的能力。课程设计是对我们的学习很有利的一个环节， 在这个阶段，我们学会把理论与实际的结合、懂得人与人沟通的重要性，通过这次课程设计中，我加深了对课本知识的理解。四、用户手册：本 程 序 在 Vi sual C + 6. 0 下 运 行 。先输入前序遍历序列，回车，再输入中序遍历序列，再回车，即可得出结果。五、运行结果：六、源程序清单：#include <stdio.h>#inc

15、lude <Stdlib.h>#include <string.h>#define MaxSize 50 typedef struct Node char data;struct Node *LeftChild;struct Node *RightChild;BiTNode;void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)->LeftChild=NULL;(*root)->RightChild=NULL;void Visit(char item)printf

16、("%c",item);void PreOrder(BiTNode *T,void Visit(char item)if(T!=NULL)Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);void InOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);v

17、oid PostOrder(BiTNode *T,void Visit(char item)if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);void PrintBiTree(BiTNode *T,int n)int i;if(T=NULL) return;PrintBiTree(T->RightChild,n+1);for(i=0;i<n;i+) printf(" ");if(n>=0) printf("

18、 ");printf("%cnn",T->data);PrintBiTree(T->LeftChild,n+1);void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame) while(prepre_f!=insame)/ 在中序序列中找到根节点same+;interval+;if(interval=0)&&(pre_f=pre_l)

19、 / 找到了叶节点，也是递归出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同时存在左子树和右子树T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pr

20、e_f+interval,in_f,in_f+interval-1,p re,in);CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);if(interval!=0)&&(interval=pre_l-pre_f)/只有左子树T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,pre,in);T->RightChild=NULL;if(interval=0)&&(pre_f!=pre_l)/ 只有右子树T->RightChild=(BiTNode *)malloc(sizeof(BiT