数据结构实验_BST查找树

《数据结构实验_BST查找树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUNANUNIVERSITY实验报告题目:BST学生姓名奎遼学生学号专业班级指导老师2012/4/29完成日期一、需求分析（1）利用二义査找数（BST）实现一个动态查找表（2）输入格式：n//BST的节点个数//n个数据m//耍査找的数据输出格式查找成功x〃返回成功和查找时比较的次数查找不成功x〃返回成功和查找时比较的次数（3）测试数据：输入：8//BST的节点个数34,76,45,I&26,54,92,65//8个数据45〃查找45输出：查找成功3〃返回成功和查找时比较的次数34〃査找34输；lh查找成功1〃返回成功和查找时比较的次数100〃查找100输岀：查找不成功3

2、〃返回成功和查找时比较的次数二、概要设计抽象数据类型数据对象：杳找表中元素为整数数据关系：满足二叉树所要求的基本关系。另外，每个节点如果有左子树，则左子树中任意元素小于该节点值，如果有右子树，则右子树中任意元素大于该节点值基木操作：BST的部分基木操作，包括初始化二叉树、初始化节点，插入节点、查找和销毁等操作。算法的基本思想根据题冃要求，用二叉查找树來实现动态查找表。插入元素e时，先判断该二叉树是否为空，若为空，将e作为该二义树的根节点。否则，从根节点开始，比较e与节点n的人小。如果e的值更小，判断n的左了树是否为空，若为空,将e作为节点n的左孩了并返回e,否则比较e与n左

3、孩子的值，依此循环下去；如果e的值更大，判断n的右子树是否为空，若为空，将e作为节点n的右孩子并返回e,否则比较en右孩子的值，依此循环下去。查找元素的算法与插入算法大同小异，从根节点开始，比较e与节点n的大小，若相等，返回True；如果e比节点n的值小，判断n的左子树是否为空，若为空，返回False,不为空则比较e与n左孩子的值，依次循环下去；如果e比节点n的值大，判断n的右子树是否为空，若为空，返回False,不为空则比较c与n右孩了的值，依次循环下去。查找过程屮，利用变量i记录比较次数。程序的流程程序由三个模块组成：（1）输入模块：完成数据的输入，建立好二义查找树(2

4、)查找模块：判断所需查找的值是否在该BST中(2)输岀模块：输出查找成功与否，并输出比较的次数三、详细设计物理数据类型査找表中数据为整数，用C语言中的int类型保存。由于二叉査找树玩玩不是完全二叉树，利用顺序结构来实现空间利用率不高，因此二叉树用链式结构来实现。typedefintElemType;typedefintStatus;typedefstructBSTnode{ElemTypedata;structBSTnode*lchild,*rchild;)BSTnode;typedefstructBST{BSTnode*root;}BST;基本操作伪代码：StatusIn

5、itBST(BST&T)〃初始化二叉树{T.root=NULL;returnOK;}StatusInitBSTnode(BSTnode*&N)〃初始化节点{N=(BSTnode*)malloc(sizeof(BSTnode));(*N).lchild=NULL;(*N).rchild=NULL;returnOK;)StatusDestroyBST(BSTnode*&N)〃销毁BST{if(N)returnERROR;if((*N).lchild)DestroyBST((*N).lchild);if((*N).rchild)DestroyBST((*N).rchild);fr

6、cc(N);returnOK;}StatusBSTinsert(BST&T,ElemTypee)〃在BST屮插入元素e{BSTnodeInitBSTnodc(N);(*N).data=e;if(T.root==NULL){T.root=N;returnOK;)M=T.root;while(l){if(e<(*M).data){if((*M).lchild==NULL){(*M).lchild=N;returnOK;}elseM=(*M).lchild;}else{if((*M).rchild==NULL){(*M).rchild=N;returnOK;}elseM=(*M)

7、.rchild;}}}StatusBSTfind(BSTT,ElcmTypcc,int&n)〃在BST中查询元素e,用n记录比较的次数〃查询成功返回OK,否则返回ERROR{n=();BSTnodc*M=T.root;while(l){n++;if(e<(*M).data){if((*M).lchild==NULL)returnERROR;M=(*M).lchild;continue;}if(e>(*M).data){if((*M).rchild==NULL)returnERROR;M=(*M).rchild;co