数据结构实验_BST查找树.doc

HUNAN UNIVERSITY实验报告题 目： BST 学生姓名 李湃 学生学号 专业班级 指导老师 完 成 日 期 2012/4/29 一、需求分析（1） 利用二叉查找数（BST）实现一个动态查找表（2） 输入格式:n /BST的节点个数/n个数据 m /要查找的数据输出格式查找成功 x /返回成功和查找时比较的次数 查找不成功 x /返回成功和查找时比较的次数（3） 测试数据：输入：8/BST的节点个数34, 76, 45, 18, 26, 54, 92, 65 /8个数据45/查找 45输出：查找成功 3 /返回成功和查找时比较的次数 34/查找 34输出：查找成功 1 /返回成功和查找时比较的次数100/查找 100输出：查找不成功 3 /返回成功和查找时比较的次数二、概要设计抽象数据类型数据对象：查找表中元素为整数数据关系：满足二叉树所要求的基本关系。另外，每个节点如果有左子树，则左子树中任意元素小于该节点值，如果有右子树，则右子树中任意元素大于该节点值基本操作：BST的部分基本操作， 包括初始化二叉树、初始化节点，插入节点、查找和销毁等操作。算法的基本思想 根据题目要求，用二叉查找树来实现动态查找表。插入元素e时，先判断该二叉树是否为空，若为空，将e作为该二叉树的根节点。否则，从根节点开始，比较e与节点n的大小。如果e的值更小，判断n的左子树是否为空，若为空，将e作为节点n的左孩子并返回e，否则比较e与n左孩子的值，依此循环下去；如果e的值更大，判断n的右子树是否为空，若为空，将e作为节点n的右孩子并返回e，否则比较e与n右孩子的值，依此循环下去。查找元素的算法与插入算法大同小异，从根节点开始，比较e与节点n的大小，若相等，返回True；如果e比节点n的值小，判断n的左子树是否为空，若为空，返回False，不为空则比较e与n左孩子的值，依次循环下去；如果e比节点n的值大，判断n的右子树是否为空，若为空，返回False，不为空则比较e与n右孩子的值，依次循环下去。查找过程中，利用变量i记录比较次数。程序的流程程序由三个模块组成：（1） 输入模块：完成数据的输入，建立好二叉查找树（2） 查找模块：判断所需查找的值是否在该BST中（3） 输出模块：输出查找成功与否，并输出比较的次数三、详细设计物理数据类型查找表中数据为整数，用C语言中的int类型保存。由于二叉查找树玩玩不是完全二叉树，利用顺序结构来实现空间利用率不高，因此二叉树用链式结构来实现。typedef int ElemType;typedef int Status;typedef struct BSTnode ElemType data; struct BSTnode *lchild, *rchild;BSTnode;typedef struct BST BSTnode *root;BST;基本操作伪代码：Status InitBST(BST &T)/初始化二叉树 T.root=NULL;return OK;Status InitBSTnode(BSTnode * &N)/初始化节点 N=(BSTnode *)malloc(sizeof(BSTnode); (*N).lchild=NULL;(*N).rchild=NULL;return OK;Status DestroyBST(BSTnode * &N)/销毁BST if(N) return ERROR;if(*N).lchild) DestroyBST(*N).lchild); if(*N).rchild) DestroyBST(*N).rchild); free(N); return OK;Status BSTinsert(BST &T,ElemType e)/在BST中插入元素e BSTnode *N,*M; InitBSTnode(N); (*N).data=e; if(T.root=NULL) T.root=N; return OK; M=T.root; while(1) if(e(*M).data) if(*M).lchild=NULL) (*M).lchild=N;return OK; else M=(*M).lchild; else if(*M).rchild=NULL) (*M).rchild=N;return OK; else M=(*M).rchild;Status BSTfind(BST T,ElemType e,int &n)/在BST中查询元素e，用n记录比较的次数/查询成功返回OK，否则返回ERROR n=0; BSTnode *M=T.root; while(1)n+; if(e(*M).data) if(*M).rchild=NULL) return ERROR; M=(*M).rchild;continue; if(e=(*M).data) return OK;二叉查找树实现的具体步骤:建立二叉查找树伪代码：for(i=1;i=n;i+) scanf(%d,&e); BSTinsert(T,e);查找过程伪代码： printf(请输入要查找的元素:n); scanf(%d,&e); if(BSTfind(T,e,n) printf(查找成功 %d,n); else printf(查找不成功 %d,n);输入和输出的格式及伪代码：请输入查找表的大小：/提示 printf(请输入查找表大小:n);/等待输入查找表大小 scanf(%d,&n);/等待输入查找表各个元素 for(i=1;i=n;i+) scanf(%d,&e); 请输入要查找的元素：/提示 printf(请输入要查找的元素:n);/等待输入 scanf(%d,&e);查找成功 n/查找成功 输出比较次数 printf(查找成功 %dn,n); 或者 查找不成功 n