《华南农业大学信息学院数据结构--课程设计报告》由会员分享，可在线阅读，更多相关《华南农业大学信息学院数据结构--课程设计报告（13页珍藏版）》请在金锄头文库上搜索。
1、华南农业大学信息学院设计性、综合性实验起止日期:_ 学院学院信息学院专业班级专业班级学号学号姓名姓名 实实 验验 题题 目目实现二叉排序树的各种算法设计性 综合性 算法设计算法设计独立完成情况独立完成情况算法熟练程度算法熟练程度项项 目目成功失败独立帮助掌握了解不懂测试测试 通过通过创建一棵空的二叉排序树插入新结点前序、中序、后序遍历二叉树中序遍历的非递归算法层次遍历二叉树在二叉树中查找给定关键字交换各结点的左右子树（选做）求二叉树的深度（选做）叶子结点数（选做）自自 我我 评评 价价输出树型结构（选做）成成 绩绩A-完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码 符合书写规范，
2、实验报告叙述清晰完整，有详尽的分析和总结。 B-完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述 清晰完整。 C-完成实验要求的大部分功能，实验报告良好。 D-未按时完成实验，或者抄袭。教师签名教师签名:_:_ 实验四上机实习报告实验四上机实习报告专业班级专业班级:_ 学号：学号：_ 姓名姓名:_ 完成日期完成日期:_（1）问题的描述：问题的描述：用函数实现如下二叉排序树算法： （1） 插入新结点 （2） 前序、中序、后序遍历二叉树 （3） 中序遍历的非递归算法 （4） 层次遍历二叉树 （5） 在二叉树中查找给定关键字(函数返回值为成功 1,失败 0) Input第一行：准备建树的结
3、点个数 n 第二行：输入 n 个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字Output第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 第十行：插入新结点后的二叉树的层次遍历序列 （2）数据结构的设计：数据结构的设计：为了方便移动使用链表来存储二叉树，因此设计如下数据类型表示二叉树：typedef struct BiTNode/生成树的结构体 Ele
4、mType key;/存储数据 struct BiTNode *left,*right;/左、右孩子指针 BiTNode,*BiTree;int main()/主函数 BiTree T; ElemType search1,search2,insert; T=CreateBiTree();/建立二叉树 scanf(“%d %d %d“, PreOrderTraverse(T);/先序遍历 printf(“n“);InOrderTraverse(T);/中序遍历 printf(“n“); PostOrderTraverse(T);/后序遍历 printf(“n“); if(searchBiT(T,
5、search1)=NULL)/查找函数 printf(“0n“); else printf(“1n“);/对第一个关键字进行查找 if(searchBiT(T,search2)=NULL) printf(“0n“); else printf(“1n“);/对第二个关键字进行查找 T=InsertBiT(T,insert);/插入一个新结点 PreOrderTraverse(T);/对插入后的新树进行先序遍历 printf(“n“); InOrderTraverse(T);/对插入后的新树进行中序遍历 printf(“n“); PostOrderTraverse(T);/对插入后的新树进行后序遍
6、历 printf(“n“); InOrderTraverseII(T);/对插入后的新树进行中序遍历（非递归算法） printf(“n“); LevelOrderTraverse(T);/对插入后的新树进行层次遍历 return 0; （3）函数功能、参数说明及概要设计：1、CreateBiTree();/创建二叉树函数，返回成功与否。/根据二叉排序树的特点，找出新结点在树中对应的位置，再插入树中。2、PreOrderTraverse(T);/用递归方式，前序遍历。 3、InOrderTraverse(T); /用递归方式，中序遍历。4、PostOrderTraverse(T);/用递归方式，
7、后序遍历。5、InOrderTraverseII(T);/利用栈，用非递归方式利用栈，用非递归方式，返回成功与否。/先扫描（非访问）根节点到所有左节点并将它们一一入栈，当无左节点时表示栈顶节点无左子树，然后取出这个节点，并访问它，将 P 指向刚出栈的节点到右孩子对右孩子进行同样的处理。6、searchBiT(T,search1);/查找函数，递归算法，返回成功与否。/利用中序遍历二叉树 T，依次比较每个结点的关键字。7、InsertBiT(T,insert);/插入函数，返回成功与否。8、LevelOrderTraverse(T);/利用队列，层次遍历利用队列，层次遍历，返回成功与否。/将根节
8、点入队，循环执行，出队，访问该节点，若该节点的左子节点不为空则将该节点的左子节点入队，若该节点的右子节点不为空，则该节点的右子节点入队；直到队列为空。（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 等 ty
9、pedef int ElemType;/定义元素类型typedef struct BiTNode/生成树的结构体 ElemType key; struct BiTNode *left,*right;/左右孩子指针 BiTNode,*BiTree;BiTree InsertBiT(BiTree T,ElemType key) /向树中写入数据，插入数据元素 key BiTree 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
10、-key=key; p-left=p-right=NULL; if(T=NULL) T=p; else if(keykey) f-left=p; else f-right=p; return T; BiTree CreateBiTree() /生成二叉树 BiTree T=NULL;ElemType key; int n,i; scanf(“%d“, for(i=1;ikey); PreOrderTraverse(p-left); PreOrderTraverse(p-right); void InOrderTraverse(BiTree root) /中序遍历，递归算法 BiTree p=r
11、oot; 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); retu
12、rn OK; typedef BiTree SElemType;/预定义struct SqStack/建立栈的结构体 SElemType *base; / 在栈构造之前和销毁之后，base 的值为 NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 ;Status InitStack(SqStack if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; Status Push(SqStack if(!S.base) re
13、turn ERROR; S.top = S.base + S.stacksize ; S.stacksize = S.stacksize + STACKINCREMENT; *S.top +=e; return OK; Status Pop(SqStack e=*-S.top ; return OK; Status StackEmpty(SqStack else return FALSE; Status InOrderTraverseII(BiTree T) /二叉树的中序遍历算法（非递归算法） SqStack S;/利用栈来暂时存储结点，之后再弹出 InitStack(S); BiTree
14、p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p-left; else Pop(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); else return searchBiT(t-right,key); typedef BiTre
15、e QElemType ; /定义typedef struct QueueNode/队列的结构体 QElemType data; struct QueueNode *next; QueueNode;typedef struct linkQueue QueueNode * front;/队头指针，若队列不空,指向队列头元素 QueueNode * rear;/队尾指针，若队列不空,指向队列尾元素的下一个位置 linkQueue;void InitQueue(linkQueue * q) q-front=q-rear =NULL; /构造一个空队列，无头结点 int QueueEmpty(linkQueue * Q)/判断队列是否为空队列 return (Q-front=NULL) void EnQueue(linkQueue *Q,QElemType x) /向队列插入新的元素 x QueueNode *p=(QueueNode *)malloc(sizeof(Que
