【2017年整理】数据结构实验二.doc

数据结构与算法 实验报告 实验题目： 二叉排序树 班 级： 信计141 姓 名： xx 学 号： 141021xx 完成日期： 2015-12-13 一、需求分析 输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，要求依次完成以下工作： (1) 以这n个整数生成(建立)一棵用链式存储结构存储的二叉排序树； (2) 按递增顺序输出该二叉排序树中的整数(关键字)； (3) 输入一个整数key，对该二叉排序树进行查找，若在该二叉排序树中存在这个整数key，则输出find，否则输出not find。 (4) 输入一个整数key，若该二叉排序树中不存在这个整数key，则将key插入到该二叉排序树中，使插入后仍为原性质的二叉排序树；否则不必插入； (5) 在(4)的基础上，按递减顺序输出该二叉排序树中的整数(关键字) 测试数据三组： 第一组 6 17 19 32 45 63 72 99 2 第二组 8 10 79 6 81 43 75 26 69 43 69 第三组 10 92 21 24 25 19 42 39 71 52 56 87 1 二、概要设计 1、算法思路 (1) 首先建立关键字要求各不相同的二叉排序树，则对于输入的关键字(整数)序列中的每一个整数，要在正在建立的二叉排序树中去查找是否已经存在该整数，不存在时，由查找模块返回要增加结点位置的双亲结点，根据要建立的二叉排序树的性质(左小右大)，当要增加的整数比双亲结点的整数小的话就插到其左孩子的位置，否则插到其右孩子的位置。这样重复，直到输入结束，这样，二叉排序树就建好了。 (2) 查找算法是从二叉排序树的根结点开始，根据要查找的整数，若比其当前二叉排序树结点中的整数小就进入其左孩子所在的左子树中继续有哪些信誉好的足球投注网站，否则进入其右左孩子所在的右子树中继续有哪些信誉好的足球投注网站，这过程中，每进入子树前，保存当前结点，以便带回要增加结点的双亲结点。有哪些信誉好的足球投注网站直至找到要查找的整数，用一指针带回；或有哪些信誉好的足球投注网站直至叶子结点的下方，找不到要查找的整数而使空指针带回，以便判断要查找的整数是否找到。 (3) 按递增顺序输出该二叉排序树中的整数，可直接用某种二叉树的遍历算法实现；按递减顺序输出该二叉排序树中的整数，只要对某种二叉树的遍历算法稍作修改即可。 (4) 插入算法思路和建立二叉排序树时增加一个整数的思路是一样的。 2、数据结构 typedef struct node//二叉排序树中的结点结构 { int data; //整数数据域 struct node*lchild,*rchild;//指向左右孩子的指针 }nodeb,*bitree; 3、基本操作 (1) 查找算法 void searchbst(bitree t,bitree *f,bitree *p,int key) { // 在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。 f 为 //指向双亲结点的 while(t不空且t中的整数不是要找的整数key) { 用f记录当前结点； if(要找的整数key小于t中的整数) t进入其左孩子所在的左子树； else t进入其右孩子所在的右子树； } } (2) 建立二叉排序树算法 bitree createbintree(int n) /* 建立有n个整数的二叉排序树，其二叉排序树t，用 函数值返回树根*/ {置t为空树； while(n次) { 输入整数； 查找该整数； if(该整数在当前的二叉排序树中不存在) { 申请结点； 对该结点赋以该整数； 该结点的左右指针赋空值； 根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置 // 注意当二叉排序树还是空树时情况的处理 } } 返回建好的二叉排序树t； } (3) 插入(增加)整数算法 int insertbst(bitree *t,int key) /* 在二叉排序树t中插入整数key的结点，是否 插入成功用函数值返回 */ { 在二叉排序树t中查找整数key； if(整数key在二叉排序树t中不存在) { 申请结点； 对该结点赋以该整数； 该结点的左右指针赋空值； 根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置 // 注意当二叉排序树还是空树时情况的处理