江苏大学C ++二进制排序树的构建，插入，删除和搜索（免费下载）

数据结构课程设计实验报告设计主题: 在二进制排序树中建立，插入，删除和查找学生姓名: 部门课程: 行业: 级别: 编号: 指导教师: 1.需求分析1.操作环境Microsoft Visual Studio 20082，该程序实现的功能二进制排序树的建立，插入，删除和搜索给出了一组键值，并建立了相应的二进制排序树以完成: ？删除节点. 需要实现删除根节点，叶节点和其他任意节点的功能； of插入新节点的操作； ⑶在二元排序树中搜索给定值； at随时显示操作结果. 3.程序的输入，包括输入数据格式和描述. 该程序从外部输入数据，输入数字序列并以-1结尾. 4.程序的输出及其输出格式由用户手动选择用于操作指令，并由程序内部处理，将相应结果输出到显示屏5.测试数据，如果输入的数据量程序比较大，需要给出测试数据. 用户手动输入数字序列进行数据测试. 1.设计说明1.算法设计思想. 需求，确定算法的主要模块（构建和输出二进制树，插入节点，删除节点，查找节点以及主要功能模块），为每个模块选择并构造功能，并控制变量. 最后，将模块组合在一起形成一个完整的算法，注意全局变量的选择.

2. 主要数据结构设计说明二进制排序树的主要存储结构Typedef struct TreeNode //声明数字结构{Int key; //存储关键字Struct TreeNode *向左； //存储左子树Struct TreeNode * right的指针； //存储正确的子树的指针} treeNode; 23.该程序的主要流程图开始构建二叉树: ①依次输入n个关键字②插入二叉树中③插入运算结果节点的节点搜索该点的已删除节点是否显示操作结果是否继续. 它是程序的主要模块. 需要说明流程图中出现的模块，并且输出显示插入*节点，使用递归算法插入节点*删除节点，是算法中较复杂的模块，需要确定是否用户输入的节点是根节点或叶节点，这与删除有关. 该节点在序列中的位置为3 *节点搜索，并且使用与二进制排序树中的key等于key的数据元素进行递归搜索由根指针指向；如果成功，则返回指向数据元素节点的指针；否则，返回一个空指针； 1）主要功能模块Main（）{建立n个关键字的二进制排序树并输出；从二叉树排序树中删除任何节点；在二叉树排序树中插入一个节点；在二进制排序树中递归搜索关键字；} 2）创建一个二进制排序树模块treeNode * buildTree（treeNode * head，int number）{构建n个关键字中的两个Fork排序树；从键盘输入中构建n个关键字，然后依次使用insertTree（int键）；返回到根节点；输出过程；} 43）删除模块deleteTree（int键）{从二叉树排序树中删除任何节点；它可以实现删除根节点，叶节点和其他任何节点的功能； 1.如果节点p是叶子，则直接删除该节点p； 2.如果节点p仅具有左子树，则只需重新连接p的左子树；如果节点p仅具有正确的子树，则只需重新连接p的正确子树； 3.如果节点p的左右子树不为空，则a查找节点p的右子树. 顶部的最左边节点（如果s）和该节点的父节点par； b. 将节点s的数据字段替换为删除的节点p的数据字段； c如果节点p的右子节点没有左子树，则s的右子树连接到par的右子树；否则，将s的右子树连接到节点par的左子树. d. 删除节点s；} 4）插入模块void insertTree（int键）{在二叉树中排序树，在其中插入节点s（递归算法）； 55）搜索模块treeNode * searchTree（int键）{在根指针指向的二进制排序树中递归地查找键等于键的数据元素；如果成功，则返回指向数据元素节点的指针；否则，返回一个空指针；} 5，程序的主要功能及其伪代码描述treeNode * BiSortTree :: buildTree（treeNode * head，int number）//创建一个二进制排序树{treeNode * p; //创建一个指向节点的指针p = new treeNode; // p节点是一个新节点p-> key = number; p->左= p->右= NULL; //如果（head == NULL）{return p;}，否则{6if（p-> key key）//如果p节点的值小于p的左右分支为空输入head节点的值，将P的值分配给head的左分支head-> left = buildTree（head-> left，数字）；否则head-> right = buildTree（head-> right，数字）； // //否则分配给head返回head的右分支；}} treeNode * BiSortTree :: searchTree（int键）//查找节点{return search（Head，key）；} void BiSortTree :: insertTree（int键）/ /插入节点{Head = buildTree（Head，key）;} int BiSortTree :: deleteTree（int key）//删除节点{treeNode * p; 7p = NULL; p =搜索（头，键）； if（p == NULL）{cout <<“找不到密钥”;} if（p == Head）{Head = NULL;} else {treeNode * parent;父= searchParent（Head，p）; if（p-> left == NULL && p-> right == NULL）//叶子节点，即p的左右子树为空{if（parent-> left == p）// if（ ！parent）{parent-> left = NULL;} else8 {parent-> right = NULL;}} else //非叶节点{if（p-> right == NULL）//节点没有右子节点{ if（parent-> left == p）{parent-> left = p-> left;} else {parent-> right = p-> left;}} else //该点具有左右子元素{treeNode * rightMin儿子，*第二父母； // secondParent是右侧子树中最小节点的父亲rightMinSon = searchMinRight（p-> right）; 9secondParent = searchParent（p-> right，rightMinSon）; secondParent-> left = rightMinSon-> right; if（p-> right == rightMinSon）//右子树中最小节点的父亲是p {p-> right = rightMinSon-> right;} p-> key = rightMinSon-> key;}}}返回1;} treeNode * BiSortTree :: searchParent（treeNode * head，treeNode * p）{if（head->左== p || head->右== p || head == p || head == NULL）回头否则{if（p->键键）返回searchParent（head-> left，p）; 10else return searchParent（head-> right，p）;}} treeNode * BiSortTree :: searchMinRight（treeNode * head）//在右侧子树中找到最小的节点{if（head-> left == NULL || head == NULL）{return head;}​​否则{return searchMinRight（head-> left）;}}机器结果和经验1.实际完成情况显示所需的基本功能: 建立二叉树，排序，插入，删除，搜索和其他操作已能够实现112. 该程序的性能分析，包括时间和空间分析操作复杂度O（n）O（n）/ O（logn）O（n）查找插入和删除3.打印初始值并运行该程序的结果，绘制相应的图标. 初始界面12a: 输入所需的树数据，并给出中间顺序序列和用户操作菜单b: 选择操作1，输出中间顺序遍历序列c: 选择操作2，插入节点，并输出中间顺序遍历d: 选择操作3，查找相关节点判断您要查找的节点是否存在13e: 选择操作4，输入要删除的节点，并输出中间序列遍历序列. 如果要删除的节点不存在，则表明该节点不存在. 4.删除部分头节点的过程中存在的问题和解决方案删除错误解决方案: 更改指针指向的节点，以确保指针指向的节点的顺序正确. 5.可以改进的地方程序显示在树构建阶段可以使用二叉树. 此程序中使用的输出格式是在输出前输出二叉树中间顺序遍历. 输出是已排序的中间顺序序列. 二叉树的输出形式不直观.

6. 收获和经验1）设计程序时要注意模块的划分，并从每个小模块开始设计2）精通每个功能成员的组成3）交流与合作14打印源程序列表并附加注释1 ，#include 2，#include 3，使用命名空间std; 4，typedef struct TreeNode // //声明树5的结构，{6，int键； //存储关键字7，struct TreeNode * left; //存储左子树8的指针，struct TreeNode * right; //存储右子树的指针9，} treeNode; 10、11、12、13、14、15、16、17、18、19、20、21、22、23，小节点24、25、26、27、28、29、30、31、32、33， 34、35、36、37、38、39，}}} {cout <<“构建一个二进制排序树，请输入您要构建的所有数字（以-1作为结束符号！）: “ << endl; //循环输入调用BuildTree函数Head = NULL;整数cin >>号; while（number！= -1）{Head = buildTree（Head，number）; cin >>数字；}; BiSortTree :: BiSortTree（）void showTree（treeNode * head）; //显示void destroyTree（treeNode * head）; //删除treeNode * Head; class BiSortTree {public: BiSortTree（void）; void desplayTree（void）; //显示这棵树void insertTree（int key）; //在树节点中插入一个int deleteTree（int键）； //删除树中的节点treeNode * searchTree（int键）； //在树中找到一个节点〜BiSortTree（）;私有: treeNode * buildTree（treeNode * head，int number）; //创建一个树treeNode *搜索（treeNode * head，int键）； //查找treeNode * BiSortTree :: searchParent（treeNode * head，treeNode * p）; //查找p treeNode * BiSortTree的父节点的指针:: searchMinRight（treeNode * head）; //找到最多的1540、41，有序树42、43、44、45、46、47、48、49、50、51、52、53、54、55、56、57、58、59、60、61 ，62，63，64，65，66，67，68，69，70，71，72，73，74，75，76，77，78，79，80，81，treeNode * BiSortTree ::搜索（treeNode * head，int key）//查找{如果（head == NULL）返回NULL; if（head-> key == k ey）返回头； else {if（key key）//如果要找到的关键字的值小于根节点，则在其左侧子树中搜索；否则，在其右子树中搜索. 返回搜索（头->左，键）； else return search（head-> right，key）;} treeNode * BiSortTree :: searchTree（int key）//找到一个节点并调用搜索功能{return search（Head，key）;}} void BiSortTree :: insertTree（ int key）//通过调用BuildTree函数{Head = buildTree（Head，key）;}插入一个节点，否则head-> right = buildTree（head-> right，number）; return head;}​​ else {if（p->键键）head-> left = buildTree（head-> left，数字）; {treeNode * p; p =新的treeNode; p->键=数字； p->左= p->右= NULL; if（head == NULL）{返回p; treeNode * BiSortTree :: buildTree（treeNode * head，int number）//创建一个二进制行1682、83、84、85、86、87、88、89、90、91、92、93、94、95、96， 97、98、99、100、101、102、103、104、105、106、107、108、109、110、111、112、113、114、115、116、117、118 119、120、121、122 ，123，124，125，}）int BiSortTree :: deleteTree（int键）//删除节点{treeNode * p; p = NULL; p =搜索（头，键）； // //首先通过搜索功能查找关键字if（p == NULL）//节点为空且找不到关键字{cout <<“找不到键”;} if（p == Head） //如果是头节点，则直接将其删除{Head = NULL;} else //否则，它将分为叶节点. 讨论有子节点的节点和有左，右子节点的节点{treeNode * parent; parent = searchParent（Head，p）; if（p-> left == NULL && p-> right == NULL）//叶子节点，即p的左右子树为空{if（parent-> left == p）// if（ ！parent）{parent-> left = NULL;} else {parent-> right = NULL;}} else //非叶子节点{if（p-> right == NULL）//这个节点没有右边的子节点{ if（parent-> left = = p）{parent-> left = p-> left;} else {parent-> right = p-> left;}} 17126，127，128，最小节点之父树129、130、131、132、133、134、135、136、137、138、139、140、141、142、143，点144、145、146、147、148、149、150、151152、153 ，154，155，点156，157，158，159，160，161，162，163二叉排序树的建立，164，165，}}}其他{{}}其他{}}}其他//这个有左右两个孩子点{treeNode * rightMinSon，* secondParent; // secondParent是右边的孩子rightMinSon = searchMinRight（p-> right）; secondParent = searchParent（p-> right，rightMinSon）; secondParent-> left = rightMinSon-> right; if（p-> right == rightMinSon）//右子树中最小节点的父亲是p {p-> right = rightMinSon-> right;} p-> key = rightMinSon-> key;}返回1； treeNode * BiSortTree :: searchParent（treeNode * head，treeNode * p）//如果（head-> left == p || head-> right == p || head == p || head == NULL查找父结）返回头；否则{if（p->键键）返回searchParent（head-> left二叉排序树的建立，p）;返回searchParent（head-> right，p）; treeNode * BiSortTree :: searchMinRight（treeNode * head）//向右查找If（head-> left == NULL | head == NULL）{返回头；返回searchMinRight（head-> left）; 18166、167、168、169、170、171、172、173、174、175、176、177、178、17 9、180、181、182、183、184、185、186、187、188、189、190 ，191，192，193，194，195，196，void BiSortTree :: desplayTree（void）//递归遍历输出{showTree（Head）; cout << endl;} void BiSortTree :: showTree（treeNode * Head）{if（Head！= NULL）{showTree（Head-> left）; cout << Head->键<<''; showTree（Head-> right）;}} BiSortTree ::〜BiSortTree（）//调用析构函数并使用递归删除所有新节点{cout <<“一棵树已被淘汰！！！” << endl; destroyTree（Head）;} void BiSortTree :: destroyTree（treeNode * head）{if（head！= NULL）{destroyTree（head-> left）; destroyTree（head->向右）;删除头；}} void print（）{cout <<“ *************以下是二进制排序树的基本操作cout <<” cout <<“ cout <<” cout <<“} int main（）{BiSortTree树； 1.输出二叉树2.插入节点3.查找节点4.删除节点*************” << endl; 197，<< endl; 198，<< endl; 199，<< << endl; 200，<< endl; 201、202、203、204、19205、206、207、20 8、209、210、211、212、213、214、215、216、217、218、219、220、221、222、223、224、225 ，226，227，228，229，230，231，232，233，234，235，236，237，238，239，240，241，242，243，244，245，246，247，int number; int choiceNumber;字符标志而（1）{print（）; cout <<“请选择要执行的操作（1〜4）” << endl; cin >> choiceNumber;开关（choiceNumber）{情况1: tree.desplayTree（）;打破;情况2: cout <<“请插入一个节点: ” << endl; cin >>编号； tree.insertTree（数字）; tree.desplayTree（）;打破;情况3: cout <<“请输入您要查找的节点: ” << endl; cin >>编号； if（tree.searchTree（number）== NULL）{cout <<“找不到要找到的节点” << endl;}否则{cout <<“找到要找到的节点” << endl;}打破;情况4: cout <<“请输入您要删除的号码: ” << endl; cin >>编号； tree.deleteTree（数字）; tree.desplayTree（）;打破;默认值: break;} cout <<“您是否要继续（是/否）？” << endl; cin >>标志； if（flag =='N'| flag =='n'）break;}返回1；} 248，20

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