数据结构bst的构建与查找实验报告.docx

HUNAN UNIVERSITY课程实验报告题目：BST的构建与查找学生姓名：学生学号：专业班级：指导老师：李晓鸿老师完成日期：2014年11月22号一 需求分析输入形式在该程序中，用户需要输入节点个数和节点数据以及查找的节点，节点数据间使用空格隔开，当用户输入有误时提示用户输入错误并重新输入。具体格式如下：请输入节点个数：请依次节点数据：请输入需查找的节点：输出形式若用户需查找的节点查找成功，则输出查找成功以及比较的次数，若查找不成功则输入查找失败，具体格式如下：查找成功 ，比较次数为_ 查找失败, 比较次数为_程序功能该程序可以通过使用二叉链表构建一个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的插入和检索的速率都是很高的，所以我们选用构建BST的方法来解决这项问题；2.由用户输入的节点个数及节点数据均为正整数，可使用整型数据进行存储，并构建一个BST存储这些节点数据；3.为了节约空间，使用二叉链表实现BST；4.为了能查询表中数据，定义一个二叉树节点类，其ADT设计如下：数据类型：整型数据数据关系：二叉树所对应的数据关系基本操作：int val();/返回结点的数值void setLeft(Node* ) ; /设置左结点 void setRight(Node* );/设置右结点 Node* left()const;/返回左结点 Node* right()const;/返回右结点4.为了存储这些数据，构建一个二叉查找树，其ADT设计如下：数据类型：整型数据数据关系:二叉树所对应的数据关系基本操作： void clear();/初始化操作 bool insert（const Elem&）;/插入元素的操作 bool find(const Elem&)const;/查找元素的操作 算法基本思想该算法主要包括表的构建和查询两项： 在表的构建上，通过用户输入的数据，将第一个输入的节点数据存入根节点中，从第二个节点元素开始，与根节点数据进行比较，如果该元素大于根节点的值，则与根节点的右子节点相比较，若右子节点为空，则将该元素存入这个节点，若不为空，则将该右子节点视为根节点，重复上述步骤。而若该元素小于根节点的值，则与根节点左子节点相比较，若左子节点为空，则将该元素存入这个节点，若不为空，则将该左子节点视为根节点，重复上述步骤。直到所有的输入的元素都存进表中为止； 在表的查询上，通过用户输入的查询的数值，将该数据与已建好的表的根节点相比较，比较次数+1，当两个数相等时，输出查找成功，比较次数为1。当该数小于根节点的数时，若左子节点不为空，则视根节点的左子节点为根节点，将该数据与新的根节点相比较，比较次数加1，重复上述步骤，直到左子节点为空。当该数大于根节点的数时，若右子节点不为空，则视根节点的右子节点为根节点，将该数据与新的根节点相比较，比较次数加1，重复上述步骤，直到两个数相等或者直到子节点为空时结束循环。若找到相等的元素，则输出查找成功以及相应的比较次数，若子节点为空时仍然没有查找到该元素，则输出未查找到该元素以及相对应的查找次数；程序基本流程本程序主要包括输入、 构建BST 、查询 和输出四个模块，其流程图如下：c三 详细设计物理数据类型1. 用户输入的节点个数使用int型数据进行存储，用户输入的节点的数据通过构建一个Node类进行存储，Node类详细ADT设计如下：class Nodeprivate: int data;/节点数据 Node *p1;/指向左子节点的指针 Node *p2;/指向右子节点的指针public: int val() return data;/返回结点的数值void setLeft(Node* it)p1=it; ; /设置左结点 void setRight(Node* it )p2=it;/设置右结点 Node* left()constreturn p1;/返回左结点 Node* right()constreturn p2;/返回右结点2. 采用二叉链表实现BST，二叉链表ADT设计如下：class BST private: Node* root;/根节点 public: BST()root=NULL;/构造函数 BST()delete roop;/析构函数 void clear() root=NULL;/初始化操作 bool insert(const int& it)/插入操作 Node *subroot1=root;Node *subroot2=root; if(root=NULL)root=new Node(it);/传给根节点值 while(subroot1!=NULL) subroot2=subroot1; if(itit)subroot2.setLeft(new Node (it);/设置左子节点elsesubroot2.setRight(new Node (it);/设置右子节点return true; bool find(int& it)/查找操作 Node* subroot=root; int count=0;/ while(subroot!=NULL) if(it=subroot.val()count+;return true;/查找成功 else if(itsubroot.val() subroot=subroot.Right();count+; /在右子节点进行查找return false;/查找失败算法具体步骤本算法主要包括以下几个模块：1. 输入模块：cinn; for(int i=0;inum; cinFindNum;2. 构建BST模块：for(int i=0;in;i+)Tree.insert(num);/3. 查找模块：使用find函数查询该BST中是否有节点的数据为FindNum4.输出模块： if(Tree.find(FindNum)=true) cout”查找成功,比较次数为“count”次”；if(Tree.find(FindNum)=false) cout”查找失败,比较次数为“count”次”；函数关系调用 建表 for(int i=0;in;i+)Tree.insert(num);算法 true 输出“查找成功“及比较次数 查找 Tree.find(FindNum) false 输出“查找失败“及比较次数算法时空分析n个元素的BST高度约为log2n,而该算法的插入的最坏情况是在BST最底端进行插入，所以插入的时间复杂度为（log n），当用户输入规模为n个时，插入的算法时间复杂度为（n log n）。查找的时间复杂度最坏情况也是在最底端找到或者查找失败，时间复杂度为（log n）， 所以算法总时间复杂度为（n log n）。输入输出格式输入：请输入节点个数：8请依次节点数据：13 58 42 19 22 44 100 65请输入需查找的节点： 42 13 12输出：查找成功，比较次数为3查找成功，比较次数为1查找失败，比较次数为3源代码：#includeusing namespace std;class Nodeprivate:double data;Node *p1;Node *p2;public:Node(double it) data = it; p1 = NULL; p2 = NULL; ;Node() deletep1; deletep2; ;void setLeft(Node* item) p1 = item; ; /设置左结点void setRight(Node* item) p2 = item; ;/设置右结点Node* Left()const return p1; ;/返回左结点Node* Right()const return p2; ;/返回右结点double val()return data;/返回结点的数值;class BSTprivate:Node* root;/根节点public:int count;BST() root = NULL; count = 0; /构造函数/BST() deleteroot; /析构函数void clear()root = NULL;/初始化操作void insert(const double& it)/插入操作if (root = NULL) root = new Node(it); /传给根节点值Node *subroot1 = root;Node *subroot2 = root;while (subroot1 != NULL)subroot2 = subroot1;if (itval()subroot1 = subroot1-Left();elsesubroot1 = subroot1-Right();if (subroot2-val()it)subroot2-setLeft(new Node(it);/设置左子节点elsesubroot2-setRight(new Node(it);/设置右子节点int find(double& it)/查找操作count = 0;Node* subroot = root;while (subroot != NULL)if (it = subroot-val()count+; return 1;/查找成功else if (itval()subroot = subroot-Left(); count+;/在左子节点进行查找else if (itsubroot-val()subroot = subroot-Right(); count+;/在右子节点进行查找return 0;/查找失败;int judge()/对输入的合法性进行判断并返回有效的输入int temp;cin.sync(); /清空输入流缓冲区cin temp;while (1)if (cin.fail() | cin.bad() | cin.get() != n) /验证输入是否合法，其中cin.fail()和cin.bad()解决输入字符串和溢出的问题cout temp;return temp;int main()BST Tree;while (1)Tree.count = 0;int n; double num; double FindNum;co