二进制排序树的基本操作

实验61，实验目的二进制排序树的基本操作1.帮助读者复习C ++语言编程的知识. 2.熟悉二进制排序树的基本操作，学习构建二进制排序树，构建二进制排序树，并对二进制排序树执行相应的操作. [需求分析]编写一种算法，为按顺序输入的关键字序列构建二叉排序树，可以实现二叉排序树的搜索，插入和删除操作. 2.实验内容和要求[问题要求]从键盘读取一组数据，构建一个二进制排序树，然后搜索，插入，遍历并打印出操作. 测试数据元素的关键字序列. [问题分析]建立二进制排序树. 根据用户所需的二进制排序树，构建二进制排序树，根据树结构打印出二进制排序树，遍历二进制排序树，并搜索二进制排序树，包括成功和失败的情况，并给出搜索长度，插入二进制排序树. 3.算法设计该程序主要采用二叉树结构类型来表示二叉树. 其中，二叉树节点由表示关键字的1个组件组成，并且有数据字段（data），左子指针字段（Lchild）和右子指针字段（Rchild）. 该程序不仅完成创建二进制排序树的功能，还有5个子功能菜单. 由于这五个子功能都建立在二进制排序树的结构上，因此二进制排序树的创建是通过主函数main（）实现的.

五个子功能的设计描述如下: 建立一个二进制排序树. 根据系统提示，输入节点的关键字，并以-1结尾作为标识符. 该功能由Bstree Create（）函数实现. 树输出二进制排序树. 通过功能TranslevelPrint（）实现树状输出二进制排序树. 当用户选择此功能时，系统以树的形式输出用户创建的二进制排序树. 在二进制排序树中插入一个新节点. 由函数Bstree Insert（）实现. 用户选择此功能后，系统会自动将添加的新节点插入二进制排序树中，以构建新的二进制排序树. 在二进制排序树中查找节点. 由函数Bstree Search（）实现. 该函数根据对二进制排序树数组元素的平滑比较来找到关键字key. 如果搜索成功，将给出搜索长度，否则输出将没有此类节点. 遍历二进制排序树. 由功能void Traverse（）实现. 此函数按顺序输出输入数组元素. 流程图如下: 主程序模块二元排序树操作模块Main（）Main（）Insert（）Search（）Traverse（）Delete（）四，调试分析和数据测试以创建二元排序树打印二元排序树搜索五，测试结果通过测试，程序设计符合要求，并且可以正确运行#include #include #include #include #define MAXLEN 100 #define NLAYER 4 // ******二进制排序树的数据结构********** typedef struct Bstnode {int key; struct Bstnode * lchild，* rchild; } Bstnode，* Bstree； Bstree树= NULL; Bstree Create（）; Bstree插入（Bstree树，int键）； Bstree搜索（Bstree树，int键）；无效的Traverse（Bstree树）; void TranslevelPrint（Bstree bt）; //创建一个二进制排序树/// //插入//查找//遍历//树打印// ********创建一个二进制排序树********** Bstree {int键，标志= 0; Bstree树= NULL; scanf（“％d”，＆key）; while（key！=-1）{//创建一个以-1 flag = 1结尾的二进制排序树； //一一插入//标记//初始化空树Create（）tree = Insert（tree，key）; node scanf（“％d”，＆key）;} if（flag）printf（“ [零提示]二进制排序树已成功创建！\ n”）; printf（“ [零提醒]查看菜单，选择所需的操作，然后按Enter继续！”）;返回树} // ******树状打印输出二进制排序树**** **** void TranslevelPrint（Bstree bt）{//此算法实现了二叉树结构节点{Bstree vec的逐层打印[MAXLEN];树节点int层[MAXLEN]；在int locat e [MAXLEN]层中；点int正面的位置，后方； } q; //定义行//打印节点//节点位置//存储列q int i，j = 1，k = 0，nLocate; q.front = 0; q.rear = 0;头，尾printf（“”）; q.vec [q.rear] = bt;队列q.layer [q.rear] = 1等节点； q.locate [q .rear] = 20; q.rear = q.rear + 1; while（q.front key）; q.front = q.front + 1; if（bt-> lchild！= NULL）//存储在左子树中，并在左子树中扎根Point like queue {q.vec [q.rear] = bt-> lchild; q.layer [q.rear] = i + 1; q.locate [q.rear] =（int）（nLocate-pow（2，NLAYER-i-1））; q.rear = q.rear +1;} if（bt-> rchild！= NULL）子树，将正确的子树根节点放入队列{q.vec [q.rear] = bt-> rchild; //存储右边//使用交点q.layer [q.rear] = i + 1; q.locate [q.rear] =（int）（nLocate + pow（2，NLAYER-i-1））; q.rear = q.rear + 1;}} printf（“ \ n【零提醒】要查看菜单，请选择所需的操作，然后按Enter继续！\ n”）; } // ** **************** INSERT ****************** Bstree插入（Bstree树，int键）{ Bstree p =树； Bstree s，f;而（p！= NULL）{f = p; if（key == p-> key）返回树； if（key key）p = p-> lchild; else p = p-> rchild;} s =（Bstree）malloc（sizeof（Bstnode））; s-> key = key; s-> lchild = NULL; s-> rchild = NULL; if（tree == NULL）{Tree = s; node return s;} //新节点是二进制排序树的根if（key key）f-> lchild = s;否则f-> rchild = s; return tree;} // //分配给根// **************查找**************** Bstree搜索（Bstree树，int键）{Bstree p = tree; int标志= 0; int i = 1; if（p == NULL）{printf（“ [零提醒]请先创建一个二叉树，然后执行搜索操作！”）; return p;} while（p！= NULL）{if（p-> key == key）{printf（“ [零提醒]查询此节点！其长度为％d \ n”二叉排序树 建立，i）; printf（“ [零提醒]请从菜单中选择所需内容，然后按Enter键继续！\ n”）；标志= 1; return（p）;打破; } i ++; if（key key）p = p-> lchild; else p = p-> rchild;} if（flag == 0）{printf（“ [零提醒]找不到带有关键字％d！\ n”，key的节点）； printf（“ [零提醒]，请参阅菜单，请选择您需要的操作，然后按Enter继续！\ n”）；返回NULL;}} // ***************遍历************** ****** int i = 1； void Traverse（Bstree tree）{//如果进行递归，则避免多重输出if（Tree == NULL && i）{printf（“ [零提醒]请先创建一个二叉树，进行Traverse操作！”）; return;} if（tree）{i = 0;遍历（tree-> lchild）; printf（“％d \ t”，t ree-> key）; Traverse（tree-> rchild）;}} // *************主要功能***************** ** void main（） {Bstree tree = NULL，p; int key1，key2，key3; int printf（“ select，flag; ___________________________________________________________ ___ \ n”）； printf（“ | | \ n”）; printf（“ | -----------------欢迎使用二进制排序树的基本操作过程--------------- | \ n” ）; printf（“ | --- __ ____ __ __ __ __ __ __ __ __ __ __ __ __ __ __ --- | \ n”）; printf（“ | ---︱--- | \ n”）; printf（“ | ---︱--- | \ n”）; printf（“ | ---︱--- | \ n”）; printf（“ | ---︱--- | \ n”）; printf（“ | --- ________ _______ __________遍历操作6.退出操作3.插入操作4.查找操作1.创建二进制排序树2.打印操作----菜单选项---- QQ: 461595940 ----------- ------ | \ n“）； printf（“ | ____________________________________________________ __________ | \ n”）; printf（“ [零提醒]请输入您的选择，然后按Enter: ”）; while（select！= 6）{scanf（“％d”，＆select）; switch（select）{情况1: printf（“ [零提醒]，请输入一组数据元素，以空格分隔，并以-1结尾: \ n”）； tree = Create（）; printf（“ \ n”）;打破;情况2: printf（“【零提醒】树形图的打印输出如下: \ n”）; TranslevelPrint（tree）;打破;情况3: printf（“ [零提醒]，请插入一个新节点: ”）; scanf（“％d”，＆key1）; if（Tree == NULL）printf（“ [零提醒]请在插入前创建一个二叉树！”）;否则{Insert（Tree，key1）; printf（“ [零提醒]要查看菜单，请选择所需的操作，然后按Enter继续！”） } printf（“ \ n”）;打破;情况4: printf（“ [零提醒]，请输入搜索数据: ”）; scanf（“％d”，＆key2）; p = Search（Tree二叉排序树 建立，key2）;打破;情况5: printf（“ [零提醒]遍历后的顺序为: \ n”）；遍历（树）; printf（“ \ n [零提醒]要查看菜单，请选择所需的操作，然后按回去继续！\ n”）； break;案例6: printf（“ [零风格的作品]欢迎再次使用它！”）; flag = 0; break; default: printf（“ [零样式提醒]您的输入不正确，请重新输入: ”）;打破; }}}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-247664-1.html