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

“数据结构”的实验报告◎实验标题: 创建二进制排序树并进行搜索◎实验目的: 1.掌握使用Visual C ++ 6.0机上调试程序的基本方法； 2.掌握二叉树的创建和二叉树的搜索方法. 3.提高您分析和解决问题的能力，并在实践中理解教科书中的理论. ◎实验内容: 建立一个至少有10个顶点的二叉排序树，然后依次遍历，然后进行搜索以确定是否存在要搜索的数据. 1.需求分析1.输入形式和输入值范围: 根据提示，首先在顶点输入数据，执行搜索操作时，输入要查找的数据，然后选择下一个操作（ A.新的Fork排序树； 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谢谢您的使用！按任意键继续. 2.摘要设计1.二进制排序树也称为二进制搜索树. 如果指定了二叉树: 如果任何节点都有左子树，则左子树的每个节点的数据必须小于该节点的数据；如果任何节点具有右子树，则右子树中每个节点的数据必须大于该节点的数据.

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

②当堆栈不为空或当前节点指针p不为空时，在（K.top！= -1 || p！= NULL）{a. 如果当前节点指针p为空，请执行以下操作: 退出堆栈，由栈顶元素作为当前节点p指向的节点输出当前节点p中的数据，以便该节点指向通过当前节点p的rchild字段作为当前节点p b. 如果当前节点指针p不为空，请执行以下操作: 将当前节点指针p压入堆栈，以便将当前节点p的rchild字段指向的节点用作当前节点p}}四说明，测试分析和结果1，程序使用说明: （1）程序的运行环境为Visual C ++ 6.0； （2）按照界面上的提示进行操作: 输入多个数据时，请用空格分隔，然后每次按Enter表示输入结束. 2.测试结果和分析: 请输入顶点数据: 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感谢您的使用！按任意键继续. 从上面的测试结果分析看，程序功能满足问题的要求.

3. 调试过程中遇到的问题和解决方案. 该实验中的错误主要发生在二叉排序树搜索中. 循环操作的条件不完整，并且输出数据的条件不正确. 发生错误. 原因是，当p为空时，仍然判断p中的数据是否等于要找到的数据. 此外，该实验中的其他小错误也得到了迅速纠正. 4.操作界面5.实验总结实验是预先准备好的. 老师在教室里做了详细的解释，所以实验比较顺利. 我于11月23日完成了该实验. 对于此实验，我非常感谢老师和同学们为我提供的指导. 通过这个实验，我对二进制排序树有了更深入的了解，学习了如何使用二进制排序树来查找数据，并对一些细节有了更好的了解，从而获得了很多东西. 老师评论: 实验结果: 教师签名: 审阅日期: 代码: #include #include // —————————————————— — ————————————————————————— typedef struct node {char data; //数据用于将字母存储在二进制树中//二进制树节点的类型描述struct node * lchild; // lchild是指向节点struct node * rchild;的左子节点的指针. // rchild是指向节点下一层的指针} BiTNode; // —————————————— —————————————————————————————— typedef struct {BiTNode * pin [40]; int top;} SeqStack; //-———————————————————————————————————————— void Create（BiTNode * B ）{int m;字符BiTNode * p，* q; p = NULL; printf（“请输入顶点数据: ”）； while（r！='\ n'）{scanf（“％d％c”，＆m，＆r）; if（p == NULL）{B-> data = m; p = B;}否则{q =（BiTNode *）mal loc（sizeof（BiTNode））; q->数据= m; q-> lchild = NULL; q-> rchild = NULL; p = B; //申请新节点q //使数据存储在当前节点中//数据字段//使新节点q的lchild字段和rchild字段为空//对其他数据执行以下操作//输入节点数据//将第一个数据放置在根节点上，p指针指向根节点//输入回车以指示循环结束. //定义指向当前节点的指针p创建二叉排序树，指向q的指针新节点// p在开始处为空////建立二进制排序树函数//指针数组，用于存储广义表Node指针//栈顶指针//顺序栈的类型描述while（ p-> data！= Q-> data）{if（p-> data data）{//当p指针指向该节点时，该点所指向的节点中的数据和q指针均不是//如果p节点数据小于新节点q中的数据，则在（p-> rchild == NULL）p-> rchild = q时执行以下操作； p = p-> rchild;}否则{if（p-> lchild == NULL）p-> lchild = q; p = p-> lchild;}}}}} //如果p的右孩子为空，则让p的右孩子为q //将p的右孩子分配给p // // p节点数据大于new中的数据节点q，执行以下操作//如果p的左孩子为空，则让p的左孩子为q //将p的左孩子分配给p // ———————————————— ————————————————————————————无效搜索（BiTNode * B，int键） p = B; while（p！= NULL && p-> data！= key）{if（p-> data rchild; else p = p-> lchild;} if（p == NULL）printf（“找到的数据不存在\ n”，键）; //循环后，如果p为空，则不存在要查找的数据；否则，要查找的数据存在，否则为printf（“要查找的数据存在\ n”，键）； printf（“ \ n”）;} // ——————————————————————————————————————— ——— void Inorder（BiTNode * B，SeqStack和K）{printf（“中间顺序遍历结果是: ”）； BiTNode * p; p = B; while（K.top！= -1 || p！= NULL）{if（p == NULL）//如果当前节点指针p为空，请执行以下操作//提示以下结果为中间顺序遍历结果// p指针指向当前节点//堆栈不为空或当前节点时当前节点为根节点//指针p不为空时，执行以下操作//遍历二叉树//如果当前节点中的数据大于要查找的数据，则让p指向其左子节点// //如果当前节点中的数据小于要查找的数据，则p指向其右子节点//定义指向当前节点p的指针//最初p指向根节点//当p不为空并且找不到由p指向的节点的数据时当数据可用时，执行以下操作//查找函数{p = K.pin [K.top]; K.top--; printf（“％d”，p->数据）； p = p-> rchild;}否则{K.top ++; K.pin [K.top] = p; p = p-> lchild;}} printf（“ \ n”）;} // ———————————————— —————————————— ———————————————— int main（）{int key; char a ='A'，b ='B'，c; BiTNode * B; SeqStack K; K.top = -1;而（a =='A'）{B =（BiTNode *）malloc（sizeof（BiTNode））; B-> rchild = NULL; B-> lchild = NULL；创建（B）;顺序（B，K）; while（b =='B'）{printf（“输入要查找的数据: ”）; scanf（“％d”，＆键）; //输入待处理的Find数据getchar（）;搜索（B，键）； //搜索//申请根节点//使根节点B的lchild字段和rchild字段为空//创建一个二元排序树///在二叉树遍历中对数据进行排序// B表示查找数据操作/ / A表示创建新的二进制排序树//定义根节点指针//定义堆栈并初始化堆栈//使当前节点的rchild字段指向的节点p当前节点p //当前节点将指针p推入堆栈// //如果当前节点指针p不为空，请执行以下操作// //在当前节点p中输出数据// //使当前节点p的rchild字段指向的节点为当前节点p //从堆栈中移出，堆栈顶部元素指向的节点用作当前节点pprintf（“选择操作（A.新的二进制排序树； B. 继续搜索； C. 结束操作）: ”）； scanf（“％c”，＆c）; printf（“ \ n”）; b = c;} a = c; b ='B';} printf（“感谢您使用！\ n”）； //根据提示，选择下一个操作返回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 loss输入要搜索的数据: 54对要搜索的数据没有选择操作（A.新的二进制排序树； B. 继续搜索； C. 结束操作）: C感谢您的使用！按任意键继续* /

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