二叉排序树的各种算法实验报告.doc

华南农业大学信息学院综合性设计实验2014学年 第二学期系别计算机科学与技术班级计机6班学号201330320614姓名赖远新实验题目实现二叉排序树的各种算法（1）自我评价完成该实验以及实验报告大概花费2天的时间，总体还算满意。自已能运用栈和队列等数据结构的特性完成特定的功能，对个结构的的特点以及运用还是比较熟悉的。但是有所欠缺的是在编码是需要参考书籍的算法例子和问同学，不能做到完全的独立编码。教师评语成绩一. 功能分析输入二叉树的结点个数n，建立二叉排序树并用链式存储结构存储二叉排序树；实现对二叉排序树的前序、中序、后序以及层次遍历；输入关键字key，在二叉树中查找，若查找成功返回值1否则返回值0；输入关键字key在二叉排序树中插入新结点。 二、数据结构总体设计1.算法分析：（1）首先我们要建立二叉排序树，对我们输入的关键字序列我们要进行边输入边插入的操作从而建立二叉排序树。在对某个待插入的关键字进行插入操作之前要在正在建立的二叉树中查找是否已经存在该关键字，不存在时由查找模块返回要插入的结点位置的双亲结点，根据二叉排序树的特点，当要插入的关键字比双亲结点的关键字小的话就插在其左孩子的位置，否则插在其右孩子的位置。这样重复操作，直到关键字序列输入完毕，二叉排序树便建立好了。（2）查找模块与查找函数都是是从二叉排序树中的根节点开始，根据要查找的整数，若比其当前二叉排序树结点中的整数小就进入其左孩子所在的左子树中继续查找，否则进入其右孩子所在的右子树中继续查找。如果查找成功则不进行插入操作，直接进行下个关键字的插入，若查找失败则在叶子节点中插入关键字。（3）遍历操作借助队列与栈等数据结构模型进行操作（4）插入新结点时和建立二叉排序树时的关键字的插入操作一样。2.二叉排序树数据结构typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3基本操作（1） 建立二叉排序树函数BiTree CreateBiT(int n) for(i=1;i=n;i+) /循环n次输入关键字序列scanf(%d,&关键字序列); 调用插入函数 InsertBiT return 二叉树;（2） 插入函数Status InsertBiT(BiTree *T,int k)while(p)在二叉树排序树中查找关键字； 若查找成功结束插入操作； 查找失败建立新结点；将该整数赋予该结点；将该结点插入某叶子结点的左孩子或右孩子中；return 1；（3） 查找函数Status Postsearch(BiTree T,int m,int &t)if(查找结点不空)if(在结点的左孩子的左子树中查找)if(在右孩子的右子树中查找)if查找成功)return 1;return 0; /查找失败elsereturn 1;（4） 主函数int main()输入关键字个数n；调用CreateBiT（n）/建立二叉排序数；建立完毕后：前序遍历；中序遍历；后序遍历；输入查找关键字m1； 查找成功输出1，否则输出0；输入查找关键字m2；查找成功输出1，否则输出0；输入要插入的关键字；插入操作结束后：前序遍历；中序遍历；后序遍历；非递归中序遍历；层次遍历；return