欢迎来到天天文库
浏览记录
ID:41689977
大小:76.95 KB
页数:5页
时间:2019-08-30
《数据结构实验_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
此文档下载收益归作者所有