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

HUNAN UNIVERSITY 实验报告 题 目： BST 学生姓名 李湃 学生学号 专业班级 指导老师 完 成 日 期 2012/4/29 一、需求分析 利用二叉查找数（BST）实现一个动态查找表 输入格式: n //BST的节点个数 //n个数据 m //要查找的数据 输出格式 查找成功 x //返回成功和查找时比较的次数 查找不成功 x //返回成功和查找时比较的次数 测试数据： 输入： 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右孩子的值，依此循环下去。查找元素的算法与插入算法大同小异，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;