资源描述：
《数据结构bst的构建与查找实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、HUNANUNIVERSITY课程实验报告题目：BST的构建与查找学生姓名：学生学号：专业班级：指导老师：李晓鸿老师完成日期：2014年11月22号一．需求分析输入形式在该程序中，用户需要输入节点个数和节点数据以及查找的节点，节点数据间使用空格隔开，当用户输入有误时提示用户输入错误并重新输入。具体格式如下：请输入节点个数：请依次节点数据：请输入需查找的节点：输出形式若用户需查找的节点查找成功，则输出查找成功以及比较的次数，若查找不成功则输入查找失败，具体格式如下：查找成功，比较次数为__查找失败,比较次数为__程序功能该程序可以通过使用二叉链
2、表构建一个BST，并实现BST内节点的插入和查找功能测试数据1.请输入节点个数：8请依次节点数据：12,4,35,78,56,34,89,0请输入需查找的节点：89查找成功，比较次数为32.请输入节点个数：8请依次节点数据：12,4,35,78,56,34,89,0请输入需查找的节点：678查找失败，比较次数为33．请输入节点个数：c输入有误请重新输入4.请输入节点个数：8请依次节点数据：12,4,35,78,56,&,89.3,A输入有误，请重新输入一．概要设计抽象数据类型1.在本程序中，需要对插入的节点进行检索，而BST的插入和检索的速率
3、都是很高的，所以我们选用构建BST的方法来解决这项问题；2.由用户输入的节点个数及节点数据均为正整数，可使用整型数据进行存储，并构建一个BST存储这些节点数据；3.为了节约空间，使用二叉链表实现BST；4.为了能查询表中数据，定义一个二叉树节点类，其ADT设计如下：数据类型：整型数据数据关系：二叉树所对应的数据关系基本操作：intval();//返回结点的数值voidsetLeft(Node*);//设置左结点voidsetRight(Node*);//设置右结点Node*left()const;//返回左结点Node*right()cons
4、t;//返回右结点4.为了存储这些数据，构建一个二叉查找树，其ADT设计如下：数据类型：整型数据数据关系:二叉树所对应的数据关系基本操作：voidclear();//初始化操作boolinsert（constElem&）;//插入元素的操作boolfind(constElem&)const;//查找元素的操作算法基本思想该算法主要包括表的构建和查询两项：①在表的构建上，通过用户输入的数据，将第一个输入的节点数据存入根节点中，从第二个节点元素开始，与根节点数据进行比较，如果该元素大于根节点的值，则与根节点的右子节点相比较，若右子节点为空，则将该
5、元素存入这个节点，若不为空，则将该右子节点视为根节点，重复上述步骤。而若该元素小于根节点的值，则与根节点左子节点相比较，若左子节点为空，则将该元素存入这个节点，若不为空，则将该左子节点视为根节点，重复上述步骤。直到所有的输入的元素都存进表中为止；②在表的查询上，通过用户输入的查询的数值，将该数据与已建好的表的根节点相比较，比较次数+1，当两个数相等时，输出查找成功，比较次数为1。当该数小于根节点的数时，若左子节点不为空，则视根节点的左子节点为根节点，将该数据与新的根节点相比较，比较次数加1，重复上述步骤，直到左子节点为空。当该数大于根节点的数
6、时，若右子节点不为空，则视根节点的右子节点为根节点，将该数据与新的根节点相比较，比较次数加1，重复上述步骤，直到两个数相等或者直到子节点为空时结束循环。若找到相等的元素，则输出查找成功以及相应的比较次数，若子节点为空时仍然没有查找到该元素，则输出未查找到该元素以及相对应的查找次数；程序基本流程本程序主要包括输入、构建BST、查询和输出四个模块，其流程图如下：c一．详细设计物理数据类型1.用户输入的节点个数使用int型数据进行存储，用户输入的节点的数据通过构建一个Node类进行存储，Node类详细ADT设计如下：classNode{privat
7、e:intdata;//节点数据Node*p1;//指向左子节点的指针Node*p2;//指向右子节点的指针public:intval(){returndata;};//返回结点的数值voidsetLeft(Node*it){p1=it;};//设置左结点voidsetRight(Node*it){p2=it};//设置右结点Node*left()const{returnp1;};//返回左结点Node*right()const{returnp2;};//返回右结点}2.采用二叉链表实现BST，二叉链表ADT设计如下：classBST{pri
8、vate:Node*root;//根节点public:BST(){root=NULL;}//构造函数~BST(){deleteroop;}//析构函数voidcle
