第九组数据结构课程设计（二进制排序树的实现）

黄淮学院信息工程学院“数据结构”课程设计报告设计方向: 二进制排序树的实现课程: 软件工程15讲师: 王阳时间: 2016.12.27二进制排序树的实现1.设计任务1）实现二进制排序树，包括生成，插入和删除； 2）对二进制排序树的第一，中间和最后根执行非递归遍历； 3）每次显示和修改树. 结果需要以树的形式表示. 4）使用二元排序树和数组来存储班级（超过50人）的成员信息（至少包括学生人数，姓名和年级），比较搜索效率，并解释二元排序树为何有效（或低）. 2.程序设计流程图（设计思路）遍历二进制排序树，并输出结果二进制列表作为存储结构，并输出序列表作为存储结构. 输入序列L，然后输入（'\\ n'）以生成输入结束标志. 二进制排序树T;找到该节点的节点，删除该节点，并按输入元素x的顺序遍历无节点x，找到二进制行的详细设计思想: 使用边缘搜索和插入的方式构建二进制排序树. 搜索功能使用递归方法进行搜索. 如果找到等于，则插入其左子树. 然后使用insert函数将元素插入到原始树中. 递归函数用于二叉树的中阶遍历. 如果根节点不为空，请先访问左侧的子树，然后再访问根节点，最后是右侧的子树.

使用删除时搜索的方法删除节点功能. 如果找不到，则提示；如果找到节点，则将其左子树的最右节点的数据传递给它，然后删除其左子树的最右节点. 3.功能模块: 3.1. 主要功能主要模块功能1.通过bstreeCreatTree（）操作建立二进制排序树. 2.通过操作bstreeInsertBST（bstreet，int键，nametypename，double grade）在二进制排序树t中插入一个节点. 通过操作void Delete（bstree＆p）从二进制排序树t中删除任何节点. 4.通过在二进制排序树中操作bstnode * SearchBST（bstreet，keytype键）查找节点. 5.通过操作p = SearchBST（t，key）查询和修改二进制排序树t中的节点信息. 6.非递归遍历二进制排序树. 7.定义函数void compare（）以比较和比较数组和二进制排序树的搜索效率. 3.2创建二进制排序树CreatTree模块从键盘输入关键字和记录，并同时调用insert函数并连续插入. 最后二叉排序树构造，返回到根节点T. 3.3删除模块: 删除二进制排序树上的阶段等同于删除有序序列中的一条记录，只要删除节点后二进制排序树的性质仍然存在即可.

假定二进制排序树中已删除的节点是* p（指向该节点的指针是p），其父节点是* f（该节点指针是f）. 如果* p节点是叶节点，则左侧和右侧是空树. 由于删除叶节点不会破坏整个树的结构，因此只需要修改其父节点的指针即可. 如果* p节点只有左子树或只有右子树，只要左或右子树直接是其父节点* f的左子树；如果* p节点的左右子树不为空，则可以让* p子树为* s的右边子树. 其次，您可以使* p的直接前任（或直接后继）替换* p，然后从二进制排序树中删除其直接前任（或直接后继）. 删除二进制排序树中的节点的算法为voidDeleteData（bstree＆t，keytype key）如果二进制排序树t中存在一个具有等于key的键的数据元素，则删除该数据元素节点并返回TRUE，否则返回FALSE . 3.4插入模块二进制排序树是一个动态树表，其特征在于树的结构通常不是一次生成的，而是在搜索过程中，当树中没有等于给定值的关键字时的节点，插入. 新插入的节点必须是新添加的叶节点，并且是搜索失败时在搜索路径上访问的最后一个节点的左或右子节点. 通过构建二进制排序树，可以将无序序列转换为有序序列. 构造树的过程是对无序序列进行排序的过程，每个插入的节点在二进制排序树上都是新的. 的叶子节点在插入时无需移动其他节点，只需更改节点的指针从空到非空.

二进制排序树的插入算法为bstreeInsertBST（bstreet，intkey，nametypename，double grade）如果二进制排序树中没有键等于键的数据元素，请插入该元素并返回TRUE. 3.5搜索模块二进制排序树也称为二进制搜索树. 当二进制排序树不为空时，首先将给定值与根节点的关键字进行比较. 如果它们相等，则搜索成功，否则将基于给定的值. 分别在左或右子树上搜索值和根节点键之间的大小关系. 为此，将用于二进制排序树的搜索算法定义为bstnode * SearchBST（bstreet，keytype key）. 在根指针t指向的二进制排序树中，找到其键等于键的数据元素. 如果成功，则返回指向元素Pointer的节点，否则返回空指针. 3.6二进制排序树的遍历顺序遍历也称为预根遍历. 首先访问根节点，然后遍历左侧子树，最后遍历右侧子树. 当遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树，如果二叉树为空，则返回. 实际上，过程是: 首先遍历左子树的根-> left-> left-> left ...-> null，因为它是一个顺序遍历，所以当遇到一个节点时，需要立即访问；因为您去过左边，所以您需要逐渐返回到父节点才能访问右边的节点，因此必须有一种措施来回溯节点序列.

一个人可以使用堆栈存储器来保存访问期间依次遇到的节点. 根据堆栈的特征，先进先出，后进先出. 您可以使用堆栈进行保存. 每次遇到的节点被推入堆栈时，遍历左子树时，从堆栈中弹出最后访问的节点，然后访问右子树. 基本算法思想: 1.首先访问根节点并将根节点放在堆栈上. 2.重复两个步骤: 如果该节点的左子节点存在，则访问左子节点并将其指针放在堆栈上. 重复上述操作，直到该节点的左子节点不存在. 将元素（即其指针）推到栈顶，回到父节点. 如果指针节点的右子节点存在，请重复上述步骤，直到指针指向的右子节点，直到桟为空. 操作函数为void x_print（树中阶遍历: 中阶遍历的顺序与一阶遍历访问的顺序不同. 中阶遍历访问顺序为左子数的中阶遍历. 在根节点处，最后是右子树的中间顺序遍历，首先顺序遍历是先访问，然后压入堆栈；而中间顺序遍历是在访问之前先堆栈并弹出堆栈. 将二叉树的根节点放在堆栈上，如果该节点具有左子节点，则将左子节点直接推入堆栈，重复该操作，直到节点中没有左子节点；在弹出该树的顶部元素之后堆栈并访问该节点所指向的节点，如果存在指针所指向的右子节点，则当前指针将指向右子节点. 重复这些步骤，直到堆栈为空操作函数为空z_print（Tree post-顺序遍历: 向左遍历顺序排列子树，然后按顺序遍历右边的子树，最后访问根节点.

首先将根节点放在堆栈上. 如果该节点的左子节点存在，则将该节点的左子节点放在堆栈上. 重复此操作二叉排序树构造，直到该节点的左子节点为空. 取栈顶元素并将其分配给P. 如果P的右子元素等于q（即，如果p的右子元素已被访问，则访问根节点，该节点指向该节点，并使用q记录刚访问过的节点的指针），如果p有一个正确的孩子，而没有访问正确的孩子，则p = p-> rchild. 操作函数为void h_print（树4. 源代码#include使用consolepauser程序，自己的getch，system（“暂停”）inputloop#include#include #include #include #include #include使用命名空间std； typedef字符串名称类型； typedef无符号长键类型； typedefstruct node //节点的结构keytypekey; nametype name; int grade; struct node * lchild，* rchild;} bstnode; typedefbstnode * bstree; //堆栈的定义// typedefstruct {bstree * base; bstree * top; intstacksize;} Sqstack; intInitStack（Sqstack＆s）sizeof（int））; s.top = s.base;返回intPush（Sqstack＆s，节点* s.top = e; s.top = s.top + 1;返回intPop（Sqstack＆s，bstree＆e）elses.top = s.top-1; e = * s.top;返回//非递归遍历和输出节点信息/// * --------------- preorder非递归遍历--------------- * / voidx_print （节点InitStack（s）; bstnode Push（s，p）; cout

键

key>键; if（key == 0）cin >> name; cin >> grade; while（key）t = InsertBST（t，key，name，grade）; printf（“请输入---学习编号-名称-等级-（输入0时结束: \ n”） ; cin >> key; if（key == 0）中断; cin >>名称； cin >>等级; // -------------------删除树中的节点------------------- // void删除（bstree＆p）bstreeq，s; if（！p-> rchild）elseif（！p-> lchild）p = p-> rchild;删除s = p-> lchild; while（s-> rchild）10q-> rchild = s-> lchild;否则q-> lchild = s-> lchild;删除voidDeleteData（bstree＆t，keytypekey）printf（“没有此类信息，请重新输入！\ n”）; cin >> key; DeleteData（t，key）;删除（t）; printf（“删除成功！\ n”）; elseif（t-> key> key）DeleteData（t-> lchild，key）;否则DeleteData（t-> rchild，key）; //二叉树的深度intTreeDepth（bstree intleft，right，max; if（t！= NULL）left = TreeDepth（t-> lchild）; right = TreeDepth（t-> rchild）; max = left> right？left: right; return max + 1;} else //树输出二叉树voidPrintTree（bstreet，int layer）11int if（t == NULL）return PrintTree（t-> rchild，layer + 1）; for（k = 0; kkey

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