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

《华南农业大学信息学院数据结构--课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华南农业大学信息学院设计性、综合性实验起止日期:______学院信息学院专业班级学号姓名实验题目实现二叉排序树的各种算法<一>√设计性□综合性自我评价项目算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂创建一棵空的二叉排序树√√√√插入新结点√√√√前序、中序、后序遍历二叉树√√√√中序遍历的非递归算法√√√√层次遍历二叉树√√√√在二叉树中查找给定关键字√√√√交换各结点的左右子树（选做）√√√√求二叉树的深度（选做）√√√√叶子结点数（选做）√√√√输出树型结构（选做）成绩

2、lA---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。lB---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。lC---------完成实验要求的大部分功能，实验报告良好。lD---------未按时完成实验，或者抄袭。教师签名:______实验四上机实习报告专业班级:___________学号：_________姓名:______完成日期:_______（1）问题的描述：用函数实

3、现如下二叉排序树算法：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)Input第一行：准备建树的结点个数n第二行：输入n个整数，用空格分隔第三行：输入待查找的关键字第四行：输入待查找的关键字第五行：输入待插入的关键字Output第一行：二叉树的先序遍历序列第二行：二叉树的中序遍历序列第三行：二叉树的后序遍历序列第四行：查找结果第五行：查找结果第六行~第八行：插入新结点后的二叉树的先、中、序遍

4、历序列第九行：插入新结点后的二叉树的中序遍历序列(非递归算法)第十行：插入新结点后的二叉树的层次遍历序列（1）数据结构的设计：为了方便移动使用链表来存储二叉树，因此设计如下数据类型表示二叉树：typedefstructBiTNode//生成树的结构体{ElemTypekey;//存储数据structBiTNode*left,*right;//左、右孩子指针}BiTNode,*BiTree;intmain()//主函数{BiTreeT;ElemTypesearch1,search2,insert;T

5、=CreateBiTree();//建立二叉树scanf("%d%d%d",&search1,&search2,&insert);PreOrderTraverse(T);//先序遍历printf("");InOrderTraverse(T);//中序遍历printf("");PostOrderTraverse(T);//后序遍历printf("");if(searchBiT(T,search1)==NULL)//查找函数printf("0");elseprintf("1");/

6、/对第一个关键字进行查找if(searchBiT(T,search2)==NULL)printf("0");elseprintf("1");//对第二个关键字进行查找T=InsertBiT(T,insert);//插入一个新结点PreOrderTraverse(T);//对插入后的新树进行先序遍历printf("");InOrderTraverse(T);//对插入后的新树进行中序遍历printf("");PostOrderTraverse(T);//对插入后的新树进行后序遍历pr

7、intf("");InOrderTraverseII(T);//对插入后的新树进行中序遍历（非递归算法）printf("");LevelOrderTraverse(T);//对插入后的新树进行层次遍历return0;}（1）函数功能、参数说明及概要设计：1、CreateBiTree();//创建二叉树函数，返回成功与否。//根据二叉排序树的特点，找出新结点在树中对应的位置，再插入树中。2、PreOrderTraverse(T);//用递归方式，前序遍历。3、InOrderTraverse(

8、T);//用递归方式，中序遍历。4、PostOrderTraverse(T);//用递归方式，后序遍历。5、InOrderTraverseII(T);//利用栈，用非递归方式，返回成功与否。//先扫描（非访问）根节点到所有左节点并将它们一一入栈，当无左节点时表示栈顶节点无左子树，然后取出这个节点，并访问它，将P指向刚出栈的节点到右孩子对右孩子进行同样的处理。6、searchBiT(T,search1);//查找函数，递归算法，返回成功与否。//利用中序遍历二叉树T，依次比较每个结点