华南农业大学信息学院数据结构--课程设计报告.doc

华南农业大学信息学院设计性、综合性实验 起止日期:_学院信息学院专业班级学号姓名实验题目实现二叉排序树的各种算法设计性 综合性自我评价项 目算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂创建一棵空的二叉排序树插入新结点前序、中序、后序遍历二叉树中序遍历的非递归算法层次遍历二叉树在二叉树中查找给定关键字交换各结点的左右子树（选做）求二叉树的深度（选做）叶子结点数（选做）输出树型结构（选做）成绩l A-完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。l B-完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述 清晰完整。l C-完成实验要求的大部分功能，实验报告良好。l D-未按时完成实验，或者抄袭。 教师签名:_ 实验四上机实习报告专业班级:_ 学号：_ 姓名:_ 完成日期:_（1） 问题的描述：用函数实现如下二叉排序树算法： （1） 插入新结点 （2） 前序、中序、后序遍历二叉树 （3） 中序遍历的非递归算法 （4） 层次遍历二叉树 （5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input第一行：准备建树的结点个数n 第二行：输入n个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字Output第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 第十行：插入新结点后的二叉树的层次遍历序列 （2） 数据结构的设计：为了方便移动使用链表来存储二叉树，因此设计如下数据类型表示二叉树：typedef struct BiTNode/生成树的结构体ElemType key;/存储数据struct BiTNode *left,*right;/左、右孩子指针BiTNode,*BiTree;int main()/主函数BiTree T;ElemType search1,search2,insert;T=CreateBiTree();/建立二叉树scanf(%d %d %d,&search1,&search2,&insert);PreOrderTraverse(T);/先序遍历printf(n);InOrderTraverse(T);/中序遍历printf(n);PostOrderTraverse(T);/后序遍历printf(n);if(searchBiT(T,search1)=NULL)/查找函数printf(0n);else printf(1n);/对第一个关键字进行查找if(searchBiT(T,search2)=NULL)printf(0n);elseprintf(1n);/对第二个关键字进行查找T=InsertBiT(T,insert);/插入一个新结点PreOrderTraverse(T);/对插入后的新树进行先序遍历printf(n);InOrderTraverse(T);/对插入后的新树进行中序遍历printf(n);PostOrderTraverse(T);/对插入后的新树进行后序遍历printf(n);InOrderTraverseII(T);/对插入后的新树进行中序遍历（非递归算法）printf(n);LevelOrderTraverse(T);/对插入后的新树进行层次遍历return 0;（3） 函数功能、参数说明及概要设计：1、CreateBiTree();/创建二叉树函数，返回成功与否。/根据二叉排序树的特点，找出新结点在树中对应的位置，再插入树中。2、PreOrderTraverse(T);/用递归方式，前序遍历。3、InOrderTraverse(T); /用递归方式，中序遍历。4、PostOrderTraverse(T);/用递归方式，后序遍历。5、InOrderTraverseII(T);/利用栈，用非递归方式，返回成功与否。/先扫描（非访问）根节点到所有左节点并将它们一一入栈，当无左节点时表示栈顶节点无左子树，然后取出这个节点，并访问它，将P指向刚出栈的节点到右孩子对右孩子进行同样的处理。6、searchBiT(T,search1);/查找函数，递归算法，返回成功与否。/利用中序遍历二叉树T，依次比较每个结点的关键字。7、InsertBiT(T,insert);/插入函数，返回成功与否。8、LevelOrderTraverse(T);/利用队列，层次遍历，返回成功与否。/将根节点入队，循环执行，出队，访问该节点，若该节点的左子节点不为空则将该节点的左子节点入队，若该节点的右子节点不为空，则该节点的右子节点入队；直到队列为空。（4） 具体程序的实现#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100/ 存储空间初始分配量#define STACKINCREMENT 10/ 存储空间分配增量typedef int Status;/ Status是函数的类型,其值是函数结果状态代码，如OK等typedef int ElemType;/定义元素类型typedef struct BiTNode/生成树的结构体ElemType key;struct BiTNode *left,*right;/左右孩子指针BiTNode,*BiTree;BiTree InsertBiT(BiTree T,ElemType key)/向树中写入数据，插入数据元素keyBiTree f,p=T;while(p)if(p-key=key) return NULL;f=p;p=(keykey)?p-left:p-right;p=(BiTree)malloc(sizeof(BiTNode);p-key=key;p-left=p-right=NULL;if(T=NULL)T=p;elseif(keykey)f-left=p;elsef-right=p;return T;BiTree CreateBiTree()/生成二叉树BiTree T=NULL;ElemType key;int n,i;scanf(%d,&n);for(i=1;ikey);PreOrderTraverse(p-left);PreOrderTraverse(p-right);void InOrderTraverse(BiTree root)/中序遍历，递归算法BiTree p=root;if(p!=NULL)InOrderTraverse(p-left );printf(%d ,p-key );InOrderTraverse(p-right );void PostOrderTraverse(BiTree root)/后序遍历，递归算法BiTree p=root;if(p!=NULL)PostOrderTraverse(p-left );PostOrderTraverse(p-right );printf(%d ,p-key );Status visit(BiTree p)/输出结点的值printf(%d ,p-key);return OK;typedef BiTree SElemType;/预定义struct SqStack/建立栈的结构体SElemType *base; / 在栈构造之前和销毁之后，base的值为NULLSElemType *top;/ 栈顶指针int stacksize;/ 当前已分配的存储空间，以元素为单位;Status InitStack(SqStack &S)/构造一个空栈SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素if(S.top - S.base = S.stacksize )S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) return ERROR;S.top = S.base + S.stacksize ;S.stacksize = S.stacksize + STACKINCREMENT;*S.top +=e;return OK;Status Pop(SqStack &S,SElemType &e)/弹出栈S的栈顶元素if(S.top =S.base ) return ERROR;e=*-S.top ;return OK;Status StackEmpty(SqStack &S)/判断S是否是空栈，并返回值if(S.base=S.top) return TRUE;else return FALSE;Status InOrderTraverseII(BiTree T)/二叉树的中序遍历算法（非递归算法）SqStack S;/利用栈来暂时存储结点，之后再弹出InitStack(S);BiTree p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-left;elsePop(S,p);if(!visit(p) return ERROR;p=p-right;return OK;BiTNode *searchBiT(BiTree t,ElemType key)/对关键字进行查找，利用递归算法if(t=NULL|key=t-key)return t;if(key key)return searchBiT(t-left,key);elsereturn searchBiT(t-right,key);typedef BiTree QElemType ;/定义typedef struct QueueNode/队列的结构体QElemType data;struct QueueNode *next; QueueNode;typedef struct linkQueueQueueNode * front;/队头指针，若队列不空,指向队列头元素QueueNode * rear;/队尾指针，若队列不空,指向队列尾元素的下一个位置linkQueue;void InitQueue(linkQueue * q)q-front=q-rear =NULL; /构造一个空队列，无头结点int QueueEmpty(linkQueue * Q)/判断队列是否为空队列return (Q-front=NULL)&(Q-rear=NULL);void EnQueue(linkQueue *Q,QElemType x)/向队列插入新的元素xQueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);p-data=x; p-next=NULL;if(QueueEmpty(Q) /无头结点的队列Q-front=Q-rear=p;else Q-rear-next=p;Q-rear=p; QElemType DeQueue(linkQueue *Q)/若队列不空，则删除Q的队头元素QElemType x;QueueNode *p;if(QueueEmpty(Q)printf(Queue Empty!);return ERROR;p=Q-front; x=p-data; Q-front=p-next; if(Q-rear=p)Q-rear=NULL;free(p); return x;/返回删除的值xvoid LevelOrderTraverse(BiTree root)/二叉树的层次遍历BiTree p;linkQueue * q;/利用队列q=(linkQueue *)malloc(sizeof(linkQueue);InitQueue(q);p=root;if(p!=NULL)EnQueue(q,p);while(!QueueEmpty(q)p=DeQueue(q);visit(p);if(p-left!=NULL)EnQueue(q,p-left);if(p-right!=NULL)EnQueue(q,p-right);int main()BiTree T;ElemType search1,search2,insert;T=CreateBiTree();/建立二叉树scanf(%d %d %d,&search1,&search2,&insert);PreOrderTraverse(T);/先序遍历printf(n);InOrderTraverse(T);/中序遍历printf(n);PostOrderTraverse(T);/后序遍历printf(n);if(searchBiT(T,search1)=NULL)printf(0n);else printf(1n);/对第一个关键字进行查找if(searchBiT(T,search2)=NULL)printf(0n);elseprintf(1n);/对第二个关键字进行查找T=InsertBiT(T,insert);/插入一个新结点PreOrderTraverse(T);/对插入后的新树进行先序遍历printf(n);InOrderTraverse(T);/对插入后的新树进行中序遍历printf(n);PostOrderTraverse(T);/对插入后的新树进行后序遍历printf(n);InOrderTraverseII(T);/对插入后的新树进行中序遍历（非递归算法）printf(n);LevelOrderTraverse(T);/对插入后的新树进行层次遍历return 0;（5） 主界面设计及程序使用规范1、输入要创建二叉树的节点总数N2、输入N个节点数的关键字（整型）以空格区分3、输入要查找的关键字（整型）4、输入要查找的关键字（整型）5、输入要插入到关键字（整型）（6） 调试情况 1. 可能出现的特殊情况 由于没有平衡调节机制，所以当输入数据为高度单调性时，不能体现出二叉排序树的优越性，不过采用了链表存储数据，所以在最坏情况下，也不会造成存储空间的浪费。2. 测试情况 录入数据，第一行为数据总量，第一行为具体数据遍历输出，第三行为线序遍历，第四行为中序遍历，第五行后序遍历输入待查找的数（第六行、第七行），输出查找结果（第八行、第九行）输入插入的数据（第十行），插入数据后的先序遍历（第十一行），中序遍历（第十二行），后序遍历（第十三行），非递归中序遍历序列(第十四行) ，层次遍历（第十五行）（7） 算法的分析和评价及本次实验心得1. 对本程序的一般性讨论本实验采用链表来存储数据，不用考虑空间浪费，但链表不能跟顺序表那样进行随机存储，随时需要用到指针来找地址。用二叉排序树来存储数据可以方便数据的查找。用C语言写此程序，利用构造函数解决初始化时定义树为空，但在插入新数据时，还是要时刻注意创建的新节点是否有初始化。2. 心得这次实验只涉及到二叉排