数据结构_二进制排序树的实验报告

一，实验目的1.巩固和加深对数据结构课程基础知识的理解，整合在数据结构课程中学习的理论知识，完成排序二叉树程序的设计. 2.了解并掌握二叉树各种基本数据结构的定义，存储结构和相应的算法，并可以用C语言实现. 3.了解构建排序的二叉树的过程. 2.实验内容llink-rlink方法用于存储二进制排序树. 编写一个程序，该程序可以通过键盘输入来构建二进制排序树，并在建立后立即遍历屏幕显示中的结果. 3.实验环境1.硬件配置: 奔腾（R）Dual-Core9 CUP E6500 @ 2.93GHz，1.96内存2.软件环境: Microsoft Windows XP Professional Service Pack 3，Microsoft Visual C ++ 6.0 4.需求分析1.输入表单和输入值范围: 根据标题要求和提示输入一些数字，并用空格将数字与数字分开，并使用0作为终止符. 2.输出形式: 已建立的已排序二叉树的中阶遍历的结果. 3.程序可以实现的功能: 可以通过键盘输入建立二进制排序树，并在程序建立后立即遍历屏幕显示的结果. 4.测试数据: 输入45 24 53 12 28 90并用空格分隔开数字，并以0作为结束字符，例如: 输入45 24 53 12 28 90中阶遍历结果的输出为: 12 24 28 45 53 90 V.外形设计为了实现上述操作，应将该结构用作存储结构.

实现如下: 结构节点{int键； //关键字值结构节点* lchild，* rchild; //左右指针} BSTNode，* BSTree; 1.基本操作: （1）struct node {int key; //关键字值结构节点* lchild，* rchild; //左右指针} BSTNode二叉排序树 构造，* BSTree;. （2）void CreateBST（BSTree * bst）创建二进制排序树（3）void inorder（BSTree bt）递归方法遍历二进制排序树（4）void InsertBST（BSTree * bst，int键）二进制排序树Insert节点2该程序包含两个模块: （1）主程序模块； （2）创建二进制排序树，插入二进制排序树的节点，然后以递归方法遍历二进制排序树（3）模块调用图: 主程序模块创建一个二进制排序树. 二进制排序树的插入节点递归地遍历二进制排序树. 3.流程图如下: 6.详细设计1.存储类型，元素类型，结点类型: struct node {int key; //关键字值结构节点* lchild，* rchild; //左右指针} BSTNode，* BSTree;元素类型为整数和指针.

2. 每个模块的分析: （1）主程序模块: main（）{BSTree bt; printf（“请插入数字（以0作为结束标记）: \ n”）; CreateBST（＆bt）; / *构造排序的二叉树* / printf（“ \ n顺序遍历结果是: ”）;订单/ *按顺序遍历有序二叉树* / printf（“ \ n”）; getchar（）;}（2）创建一个二叉排序树函数模块void CreateBST（BSTree * bst）{int key; * bst = NULL; scanf（“％d”，＆key）; while（key！= 0）{InsertBST（bst，key）; scanf（“％d”，＆key）;}}插入二进制排序树的节点功能模块void InsertBST（BSTree * bst，int key）{BSTree s; if（* bst == NULL）{s =（BSTree）malloc（sizeof（BSTNode））; s-> key = key; s-> lchild = NULL; s-> rchild = NULL; * bst = s;} else if（key <（* bst）-> key）InsertBST（＆（（** bst）-> lchild），key）; //将s插入左子串else if（key>（* bst）-> key）InsertBST（＆（（** bst）-> rchild），key）; //将s插入正确的子字符串}递归遍历void（order）（BSTree bt）{if（bt！= NULL）{inorder（bt-> lchild）; printf（“％3d”，bt- > key）; inorder（bt-> rchild）;}} 3）函数调用图main（）CreateBST（BSTree * bst）InsertBST（BSTree * bst，int key）inorder（BSTree bt）3.完整程序: #include“ stdio.h“ #include” malloc.h“ typedef结构节点{int键； //关键字值结构节点* lchild，* rchild; //左右指针）BSTNode，* BSTree; void InsertBST（BSTree * bst，int key）//插入二进制排序树的节点{BSTree s; if（* bst == NULL）{s =（BSTree）malloc（sizeof（BSTNode））; s-> key = key; s-> lchild = NULL; s-> rchild = NULL; * bst = s;} else if（key <（* bst）-> key）InsertBST（＆（（** bst）-> lchild），key）; //将s插入左子串else if（key>（* bst）-> key）InsertBST（＆（（（** bst）-> rchild），key）; //将s插入右子字符串} void CreateBST（BSTree * bst）//创建二进制排序树{int key; * bst = NULL; scanf（“％d”，＆key）; while（key！= 0）{InsertBST（bst，key）; scanf（“％d”，＆key）;}} void inorder（BSTree bt）//在递归方法{if（bt！= NULL）{inorder（bt-> lchild）;中，printf（“％ 3d“，bt-> key）; inorder（bt-> rchild）;}} main（）{BSTree bt; printf（”请插入数字（以0作为结束符号）: \ n“）; CreateBST（＆bt ）; / *构造排序二叉树* / printf（“ \ n顺序遍历结果是: ”）;订单/ *按顺序遍历排序二叉树* / printf（“ \ n”）; getchar（）;} VII. 程序说明和测试结果1.程序说明（1）该程序的运行环境为VC6.0.

（2）进入演示程序后，出现提示信息: 请输入数字，并以0作为结束符号，然后按Enter；即获得中阶遍历排序二叉树结果2. 测试结果: 例如: 输入: 45 24 53 12 28 90输出: 12 24 28 45 53 90 3.调试中的错误和解决方案. 在调试过程中，我遇到了许多问题. 例如，当开始生成二进制排序树时，请参考本书中用于构造二进制排序树的算法，但是当将树的地址传递给函数的参数时，请运行程序. 处理. 后来，形式参数更改为BSTree * bst. 最初，BSTree bst等效于定义结构节点类型指针，并在指针上添加*作为指针. 首先在运行界面中输入45 24 53 12 28 28 90，然后按Enter: 8.实验总结: 8.实验总结: 在实验过程中我仍然遇到一些问题. 创建二进制排序树和该二进制排序树的插入节点. 点算法是指西安电子科技大学出版的耿国华老师的数据结构c语言描述. 卡编译时不正确. 稍后，在调试之后，程序可以正确运行. 简而言之，通过此测试，对树的知识仍然有更深入的了解二叉排序树 构造，例如如何构建二进制排序树. 通常，用于构建树的算法使用递归算法，但是二进制排序树是规则树，这加深了对递归算法的理解. 签名: 日期: 签名: 日期: 实验结果: 批准日期:

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