数据结构创建二进制排序树并搜索.doc

关于“数据结构”的实验报告◎实验主题: 创建二进制排序树并进行搜索◎实验目的: 1.掌握使用Visual C ++ 6.0调试机器上程序的基本方法；掌握二叉排序树的创建和第二种交叉排序树搜索方法. 提高您分析和解决问题的能力，并在实践中理解教科书上的理论. ◎实验内容: 建立一个至少有10个顶点的二叉排序树，然后依次遍历，然后进行搜索以确定是否存在要搜索的数据. 一，需求分析1.输入形式和输入值范围: 根据提示，首先在顶点输入数据. 执行搜索操作时，输入要搜索的数据，然后选择下一步要执行的操作（A.新的第二把叉子分类树； B. 继续搜索； C. 结束操作）. 2.输出形式: 输出二进制排序的中阶遍历结果. 输入要搜索的数据后，输出搜索结果. 3.程序可以做什么: 输入顶点数据后，创建一个二进制排序树，然后按顺序遍历，然后输入要搜索的数据以进行搜索操作. 4.测试数据: 请输入顶点数据: 53 25 76 20 48 14 60 84 33 78顺序遍历结果为: 14 20 25 33 48 53 60 76 78 84输入要搜索的数据: 33有一个选择操作要搜索的数据（A新的二进制排序树； B. 继续搜索； C. 结束操作）: B输入要搜索的数据: 54没有要搜索的数据的选择操作（A.新的二进制排序树; B.继续搜索； C.结束操作）: C感谢您的使用！按任意键继续II概述设计二叉排序树也称为二叉搜索树. 如果指定了二叉树: 如果任何节点都有左子树，则其左子树中每个节点的数据必须小于该节点的数据；如果任何节点具有右子树，则右子树中每个节点的数据必须大于该节点的数据.

以这种方式构造的二进制树称为二进制排序树. 通过对二进制排序树进行有序遍历而获得的节点序列是有序序列. 创建用于创建二进制排序树的非递归算法的步骤如下: ①生成一个新节点； ②与根节点进行比较. 如果它小于根节点，则沿左链域对其进行比较. 如果它大于根节点，请遵循右链域比较； ③直到终端插入节点. 以序列53、25、76、20、48、14、60、84、33、78为例，图中显示了创建的二进制排序树. 二叉树搜索的基本思想: 搜索过程从根节点开始，首先将其关键字与给定值k进行比较. 如果相等，则搜索成功并输出相关信息. 如果不相等，则如果根节点关键字大于给定值k，则继续搜索到左子树，否则继续搜索到右子树. 对子树的搜索还是树状搜索. 首先，将子树的根节点数据与k进行比较. 如果不相等，它将转向其左或右子树以继续搜索. 4.该程序的基本操作和模块: 创建二进制排序树的功能: 创建（BiTNode * B）二叉树的中间顺序遍历功能: 有序（BiTNode * B，SeqStack＆K）搜索功能: 搜索（BiTNode * B，int键）主要功能: main（）函数的调用关系如下图所示: 三个详细的设计元素类型，节点类型二叉树节点类型描述typedef struct node {char data; //数据用于将字母struct存储在二叉树节点中* lchild; // lchild是指向节点struct node * rchild;的左子节点的指针. // rchild是指向节点下一层BiTNode的指针；参照图2，顺序堆栈typedef struct {BiTNode * pin [40]的类型描述； //指针数组，用于存储广义表节点的指针int top; //堆栈顶部指针} SeqStack;每个模块的分析主程序模块main（）{①定义根节点指针②定义堆栈并初始化堆栈③申请根节点空间，并将根节点B的lchild和rchild字段留空. ④调用以创建二进制排序树函数. ⑤调用中阶遍历二叉树函数. ⑥调用搜索功能进行查找. 函数void Create（BiTNode * B）{①将指针p定义为当前节点，将指针q定义为新节点，并且p开头应为空. ②如果输入的不是回车，请执行以下操作. {输入节点数据. ◎如果数据是第一个数据{第一个数据保存到根节点，p指针指向根节点}◎如果数据不是第一个数据{①申请新节点q，则将此数据存储在数据中q的字段，以使新节点q的lchild和rchild字段为空②p指向根节点③当p指针指向的节点和q指针指向的节点中的数据不同时，执行以下操作{◎如果p节点中的数据小于新节点q中的数据，请执行以下操作{如果p的右子元素为空. 令p的右子为q并将p的右子分配给p}◎如果p节点的数据大于新节点q中的数据，请执行以下操作{如果p的左子为空，则p的左子节点将p的左子节点分配给p}}}}}搜索函数void Search（BiTNode * B，int键）{①定义了指向当前节点的指针p最初指向根节点②当p不为空且p指向的节点的数据不是要搜索的数据时，执行以下操作{如果当前节点中的数据小于要搜索的数据，则使p指向其右侧儿童. 如果当前节点中的数据大于要搜索的数据，则让p指向其左子元素. }循环结束后，如果p为空，则不存在要搜索的数据；否则，存在要搜索的数据. }按{①定义代表当前节点的指针p，并让p指代根节点的顺序遍历二叉树的功能无效显示（GLNode * G，SeqStack＆K）.

②当堆栈不为空或当前节点指针p不为空时，在（K.top！= -1 || p！= NULL）时执行以下操作{如果当前节点指针p为空，执行以下操作: 弹出堆栈，将堆栈顶部元素所指向的节点作为当前节点p，输出当前节点p中的数据，并让当前节点p的rchild字段所指向的节点作为当前节点p. 当前节点pp不为空，则执行以下操作: 将当前节点指针p压入堆栈，以便将当前节点p的rchild字段指向的节点用作当前节点. 运行的环境是Visual C ++ 6.0. 根据界面提示进行操作: 输入多个用空格分隔的数据，然后为每个输入按Enter以指示测试结果和分析的结束: 请输入顶点数据: 53 25 76 20 48 14 60 84 33序列遍历结果在78中是: 14 20 25 33 48 53 60 76 78 84输入要搜索的数据: 33对要搜索的数据进行选择操作（A.新的二叉排序树； B.继续搜索； C.结束操作）: B输入要搜索的数据: 54没有要搜索数据的选择操作（A.新的二进制排序树； B.继续搜索； C（结束操作）: C谢谢您的使用！继续以上测试结果分析的关键，程序功能满足问题的要求调试中遇到的问题及解决方案该实验的错误主要发生在二叉排序树搜索中，循环操作的条件判断不完整，以及输出的条件判断数据不正确，导致操作过程中出错.

原因是，当p为空时，仍然确定p中的数据是否等于要搜索的数据. 此外，该实验中的其他小错误也得到了迅速纠正. 操作界面V.实验总结该实验已预先预览. 老师在教室里详细解释了这一点，因此实验很顺利. 我在11月23日完成了这个实验. 对于这个实验，我非常感谢老师和同学们给我指点. 通过这个实验，我对二进制排序树有了更深入的了解，学习了如何使用二进制排序树来查找数据，并对一些细节有了更好的了解，并且学到了很多东西. 老师的评论: 实验结果: 教师签名: 审阅日期: 代码: #include #include // —————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————— ———————————————————— ———————————————————————————————————————————————————— ————————————————————————————————————————————————————二叉树节点的类型描述； * lchild; // lchild是指向节点struct node * rchild;的左子节点的指针. // rchild是指向节点下一层的指针} BiTNode; // —————————————————————————————————————————————————— ———————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————————————————————————————————————————— ———————————————— DESCRIPTION用于存储广义表节点指针的数组rs int top; //堆栈顶部指针} SeqStack; //---------- //创建二进制排序树的功能{int m;字符BiTNode * p，* q; //定义指向当前的节点指针p，新的节点指针qp = NULL; // p最初为空printf（“请输入顶点数据: ”）； while（r！='\ N'）//输入回车符以结束循环{scanf（“％d％c”，＆m，＆r）; //输入节点数据if（p == NULL）//将第一个数据设置为根节点，并且p指针指向根节点{B-> data = m; p = B;）else ///对其他数据执行以下操作（q =（BiTNode *）malloc（sizeof（BiTNode））; //申请新节点qq-> data = m; //让数据被存储在当前节点的数据字段中q-> lchild = NULL; q-> rchild = NULL; //使新节点q的lchild和rchild字段为空p = B;而（p-> data！= q- > data）//如果p指针指向的数据和q指针指向的节点不同，请执行以下操作（if（p-> data data）//如果p的数据节点小于新节点q中的数据，执行以下操作{if（p-> rchild == NULL）//如果p的右子元素为空，则让p的右子元素为qp-> rchild = q; p = p-> rchild; // p分配了正确的孩子p} else //如果p节点的数据大于新节点q中的数据，请执行以下操作{if（p-> lchild = = NULL）//如果p的左子元素为空，则使p的左子元素为qp-> lchild = q; p = p-> lchild; // lef p的t个孩子分配给了p）}）}} // —————— —————————————————————————————— ————— void Search（BiTNode * B，int key）//查找函数（BiTNode * p; //定义指向当前节点的指针pp = B; //最初p指向根节点，而（p！= NULL && p-> data！= Key）// //当p不为空且p为时当节点的数据不是要搜索的数据时创建二叉排序树，执行以下操作{if（p-> data rchild; else //如果当前节点中的数据大于要搜索的数据，则让p指向其左子节点p = p-> lchild;} if（p == NULL）printf（“要搜索的数据确实不存在\ n“，键）； //循环结束后，如果p为空，则不存在要搜索的数据；否则，要搜索的数据存在，否则为printf（“要搜索的数据存在\ n”，键）； printf（“ \ n”）;} // ——————————————————————————— ——————— void Inorder（BiTNode * B，SeqStack＆K）//二叉树的中阶遍历函数{printf（“中阶遍历结果为: ”）； //提示以下结果如果结果是有序遍历结果，则BiTNode * p; // p指针指向当前节点p = B; //当前节点是根节点，而（K.top！= -1 || p！= NULL）//当堆栈不为空或当前节点指针p不为空时，执行以下操作{ （p == NULL）///如果当前节点指针p为空创建二叉排序树，请执行以下操作{p = K.pin [K.top]; //放置堆栈，堆栈的顶部元素所指向的节点为当前节点pK.top-;. printf（“％d”，p->数据）； //在当前节点中输出数据p = p-> rchild; // //使当前节点p的rchild字段指向的节点成为当前节点p} else ///如果当前节点指针p不为空，则执行以下操作{K.top ++; //当前节点指针p被压入堆栈K.pin [K.top] = p; p = p-> lchild; //使当前节点p的rchild字段指向的节点成为当前节点p}} printf（“ \ n”）;} // —————————————— ———————————————————————— int main（）（int key; char a ='A'，b ='B'，c; BiTNode * B ; //定义根节点指针SeqStack K; //定义堆栈并初始化堆栈K.top = -1; while（a =='A'）// A表示创建新的二进制排序树（B =（ BiTNode *）malloc（sizeof（BiTNo de））; //申请根节点B-> rchild = NULL; B-> lchild = NULL; //将根节点B的lchild和rchild字段设置为空创建（B）; //创建一个二进制排序树顺序（B，K）; //遍历二进制树中的数据，而（b =='B'）// B表示查找数据操作{printf（“输入数据要找到: “）; scanf（”％d“，＆键）; //输入要查找的数据getchar（）;搜索（B，键）; //搜索printf（”选择操作（A.新建二进制排序树； B. 继续搜索； C. 结束操作ration）: “）; scanf（”％c“，＆c）; //根据提示，选择下一个操作printf（” \ n“）; b = c;} a = c; b ='B';} printf（“感谢您使用！\ N”）; return 0;} / **请输入顶点数据: 53 25 76 20 48 14 60 84 33 78顺序遍历的结果是: 14 20 25 33 48 53 60 76 78 84输入要查找的数据: 33是要搜索的数据的选择操作（A.一个新的二进制排序树； B. 继续搜索； C. 结束操作）: B输入要搜索的数据: 54没有要选择的数据的选择操作搜索（A.新的二进制排序树； B.继续搜索； C.结束操作）: C感谢您的使用！按任意键继续* /

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