BST实现动态查找表

1、HUNAN UNIVERSITY课程实习报告题 目： BST实现动态查找表 学生姓名 学生学号 专业班级 计算机科学与技术 指导老师 李晓鸿 完 成 日 期 一、需求分析 1、程序任务：本程序是利用二叉查找树（BST）来实现；二叉树使用链式结构（二叉链表）实现；本程序要实现BST的构建，查找两个功能。2、输入形式：整数n/BST的节点个数n/n个数据数据x/查找此数据3、输出形式： 查找成功 整数m（次数）/返回成功和查找时比较的次数 或：查找不成功 整数m（次数） /返回不成功和查找时比较的次数4、测试数据： 输入：8/BST的节点个数34, 76, 45, 18, 26, 54, 92,

2、65 /8个数据输入：45/查找 45 输出：查找成功 3 /返回成功和查找时比较的次数 输入：34/查找 34输出：查找成功 1 /返回成功和查找时比较的次数输入：100/查找 100输出：查找不成功 3 /返回成功和查找时比较的次数二、概要设计 抽象数据类型以正整数储存用户输入节点个数，浮点小数存储用户输入的数据。要实现动态查找表，二叉查找树BST的效率很高，因此用BST实现，二叉查找树定义如下：ADT BST数据对象：D具有相同特性的一组数据元素 数据关系：若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m

3、(m>0)个互不相交的有限集Tl、 Tr，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 (3)对于任意结点，设其值为K，则该结点左子树中任意一个结点的值都小于K， 右子树中任意一个结点的值都大于等于K。 基本操作： InitBST(BST &)/初始化二叉树InitBSTNode(BSTNode *)/初始化结点clearBST(BSTNode *)/销毁二叉树结构insert(BST &, Elem&)/插入结点find(BST &,Elem& ,int count)/查找结点,记录查找次数 ADT BST算法的基本思想根据题

4、目要求，用二叉查找树实现动态查找表。首先将输入的元素插入BST中。判断输入要查找的元素是否在BST中，递归比较要查找的元素与当前元素的值的大小，若小于当前值，则查找其左子树；若大于，则查找其右子树。设置一个计数器，每查找一次则加一。如果找到，则输出位置和查找次数。程序的流程程序由三个模块组成：（1） 输入模块：输入结点数目初始数据，构建二叉查找树（2） 查找模块：判断需要查找的值是否在该BST中（3） 输出模块：输出查找成功与否，并输出比较的次数三、详细设计算法的具体步骤插入元素e时，先判断该二叉树是否为空，若为空，将e作为该二叉树的根节点。否则，从根节点开始，比较e与节点n的大小。如果e的值

5、更小，判断n的左子树是否为空，若为空，将e作为节点n的左孩子并返回e，否则比较e与n左孩子的值，依此循环下去；如果e的值更大，判断n的右子树是否为空，若为空，将e作为节点n的右孩子并返回e，否则比较e与n右孩子的值，依此循环下去。查找元素时，从根节点开始，比较e与节点x的大小，若相等，返回true；如果e比节点x的值小，判断x的左子树是否为空，若为空，返回false，不为空则比较e与x左孩子的值，依次循环下去；如果e比节点x的值大，判断x的右子树是否为空，若为空，返回false，不为空则比较e与x右孩子的值，依次循环下去。物理数据类型动态查找表的数据为小数或整数，用float类型保存。type

6、def float ElemType;为了提高空间利用率，用链表来实现BST，由于BST是二叉树，每个节点有左右两个节点，所以用二叉链表实现。typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild;BSTNode;typedef struct BST BSTnode *root;BST;基本操作：bool InitBST(BST &b) /初始化二叉树 b.root=NULL;return ture;bool InitBSTNode(BSTNode * &n) /初始化节点 n=(BSTNode

7、 *)malloc(sizeof(BSTnode); (*n).lchild=NULL;(*n).rchild=NULL;return ture;bool clearBST(BSTNode * &n) /销毁BST if(n) return false;if(*n).lchild) clearBST(*n).lchild); if(*N).rchild) clearBST(*n).rchild); free(n); return ture;bool insert(BST &b,ElemType e)/把结点插入BST BSTNode *n,*m; InitBSTNode(n);

8、 (*n).data=e; if(b.root=NULL) b.root=n; return ture; m=b.root; while(1)/循环比较 if(e<(*m).data)/小于根节点则插入左子树 if(*m).lchild=NULL) (*m).lchild=m;/给左孩子赋值return ture; else m=(*m).lchild;continue; /跳出此次循环，开始下一次 else/大于根节点则插入右子树 if(*m).rchild=NULL) (*m).rchild=n; /给右孩子赋值return ture; else m=(*m).rchild;cont

9、inue;/跳出此次循环，开始下一次 bool find(BST b,ElemType e,int &count) /查询元素e，记录比较的次数，查询成功返回ture，否则返回false int count=0; BSTnode *x=b.root; while(1)/循环比较count+;/设置计数器 if(e<(*x).data)/小于根节点则在左子树中查找 if(*x).lchild=NULL) return false;/左子树为空则查找失败 x=(*x).lchild;/继续与左孩子的值比较continue; if(e>(*x).data) /大于根节点则在右子树

10、中查找 if(*x).rchild=NULL) return false; /右子树为空则查找失败 x=(*x).rchild; /继续与右孩子的值比较continue; if(e=(*x).data) return ture;算法的时空分析查找元素需要的比较次数由树的深度决定。因此平均情况为（log（n），最差情况为（n）。输入和输出的格式输入请输入树的节点数目：/等待输入 请输入所有节点数据：/等待输入请输入要查找的数据：/等待输入输出查找成功，查找次数：/输出次数 或查找失败，查找次数：/输出次数 四、测试结果附录：源代码#include<iostream>#include&

11、lt;stdlib.h>using namespace std;typedef float ElemType;typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild;BSTNode;typedef struct BST BSTNode *root;BST;bool InitBST(BST *b) /初始化二叉树 b->root=NULL;return true;bool InitBSTNode(BSTNode * &n) /初始化节点 n=(BSTNode *)malloc(sizeof(B

12、STNode); (*n).lchild=NULL;(*n).rchild=NULL;return true;bool clearBST(BSTNode * &n) /销毁BST if(n) return false; if(*n).lchild) clearBST(*n).lchild); if(*n).rchild) clearBST(*n).rchild); free(n); return true;bool insert(BST *b,ElemType e)/把结点插入BST BSTNode *n,*m; InitBSTNode(n); (*n).data=e; if(b-&g

13、t;root=NULL)b->root=n; return true; m=b->root; while(1)/循环比较 if(e<(*m).data)/小于根节点则插入左子树 if(*m).lchild=NULL) (*m).lchild=n;/给左孩子赋值 return true; else m=(*m).lchild; continue; else/大于根节点则插入右子树 if(*m).rchild=NULL) (*m).rchild=n; /给右孩子赋值 return true; else m=(*m).rchild; continue; bool find(BST

14、*b,ElemType e) /查询元素e，记录比较的次数查询成功返回true，否则返回false int count=0; BSTNode *x=b->root; while(1)/循环比较 count+;/设置计数器 if(e<(*x).data)/小于根节点则在左子树中查找 if(*x).lchild=NULL) cout<<"查找失败,查找次数： "<<count<<endl;return false;/左子树为空则查找失败x=(*x).lchild;/继续与左孩子的值比较 continue; if(e>(*x)

15、.data) /大于根节点则在右子树中查找 if(*x).rchild=NULL) cout<<"查找失败,查找次数： "<<count<<endl;return false;/右子树为空则查找失败x=(*x).rchild;/继续与右孩子的值比较 continue; if(e=(*x).data) cout<<"查找成功,查找次数： "<<count<<endl; cout<<count; return true; void main()int n,m=0,count;BST b;InitBST(&b);cout<<"请输入树的节点数目："<<endl;cin>>n;ElemType *