资源描述：
《数据结构课程实验报告实验6》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构课程实验指导书HUNANUNIVERSITY课程实习报告题目：BST学生姓名康小雪学生学号20090810310专业班级计科三班指导老师李晓鸿完成日期2010-12-11－5－数据结构课程实验指导书一、需求分析1．该程序可以从通过从键盘输入结点的个数和结点信息（数字）来建立一个新的二叉树，输入的数字可以不按大小顺序，但大小不能重复；2．还可以输入新的数据，计算机可通过在二叉树中比较查找是否有该数据，若有，则计算机返回“查找成功”及查找时比较的次数，若没有则返回“查找不成功”及查找时比较的次数，
2、由此形成一个动态查找表输入输出举例输入：8//BST的节点个数34,76,45,18,26,54,92,65//8个数据45//查找45输出：查找成功3//返回成功和查找时比较的次数34//查找34输出：查找成功1//返回成功和查找时比较的次数100//查找100输出：查找不成功3//返回成功和查找时比较的次数二、概要设计抽象数据类型二叉树ADTBiTree{数据对象D：D是具有相同特性的数据元素集合数据关系R：若D为空集，则R为空集，则称BinaryTree为空二叉树；若D不为空集，否则R={H}，
3、H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr}且D1∩Dr=空集；（3）若D1≠空集，则D1中存在唯一元素x1，∈H,且存在D1shangdeguanxiH1=H;ruoDr≠空集，则Dr中存在唯一的元素，xr，∈H，且存在Dr上的关系Hr∈H;H={,,H1,Hr};（4）(D1,{H1})是一棵符合本定义的二叉
4、树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树基本操作P:BoolBST::BSTSearch(intkey,int&count)//在BST中查找元素boolBST::BSTInsert(intkey)//在BST中插入一个新的元素boolBST::BSTSearchHelp(BSTNode*root,intkey,int&count)//查找的辅助函数，判断两个关键记录是否相等，若相等则返回，若大于则在右子树中查找，若小于就在左子树中查找boolBST::BSTIn
5、sertHelp(BSTNode*root,intkey,BSTNode*rootParent)//插入的辅助函数，在当前节点的左或右子树插入一个节点voidBST::BSTDestoryHelp(BSTNode*root)//销毁二叉树－5－数据结构课程实验指导书}ADTTree算法的基本思想先输入元素，构建一棵二叉树，再输入需要查找的元素，在二叉树中查找是否存在该元素。程序的流程程序由二个模块组成：（1）输入建立模块：在主函数中输入结点数和结点信息并建立相应的二叉树（2）输入查找模块：输入需要查找
6、的数据，并在二叉树中查找最后返回查找信息三、详细设计物理数据类型二叉树classBST//二叉树{private:classBSTNode{//二叉树节点BSTNode*leftChildPtr;//左孩子BSTNode*rightChildPtr;//右孩子intvalue;//值BSTNode*root;//根节点};算法的具体步骤//基本操作的函数原型BST::BST(){root=0;}//初始化根节点为0BST::~BST(){BSTDestoryHelp(root);}//析构函数销毁二叉
7、树boolBST::BSTSearch(intkey,int&count){returnBSTSearchHelp(root,key,count);}//在二叉树中查找boolBST::BSTInsert(intkey)//插入新元素{if(root==0){root=newBSTNode(key,0,0);returntrue;}returnBSTInsertHelp(root,key,0);}boolBST::BSTSearchHelp(BSTNode*root,intkey,int&count)
8、//查找{if(root==0)returnfalse;－5－数据结构课程实验指导书if(key==root->value){count++;returntrue;}elseif(keyvalue){count++;returnBSTSearchHelp(root->leftChildPtr,key,count);}else{count++;returnBSTSearchHelp(root->rightChildPtr,key,count)
