何彬实验报告

1、计算机科学与工程学院算法与数据结构实验报告(九)专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名实验时间实验项目查找技术综合应用实验类别基础性（） 设计性（） 综合性（） 其它（ ）实验目的及要求（1）熟练掌握查找的常用算法；（2）设计和应用查找算法解决比较简单的实际问题。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明： 评阅教师： 赵卿松 日 期： 2015 年 6 月 13 日实 验 内 容实验内容：二叉排序树。任意给定一组数据，设计一个算法，

2、建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;二叉排序树插入算法伪代码如下：1. 若root是空树，则将结点s作为根结点插入；否则2. 若s-dataroot-data，则把结点s插入到root的左子树中；否则3. 把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需重

3、接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s；实 验 内 容#include#include#include#define Max 100typedef int KeyType;typedef struct nodeKeyType key;struct node *lchild, *rchild;

4、 BSTNode;int InsertBST(BSTNode *&p, KeyType k)/插入关键字为k的结点 if(p=NULL)p=(BSTNode *)malloc(sizeof(BSTNode);p-key=k;p-lchild=p-rchild=NULL;return 1;else if(k=p-key)return 0;else if(kkey)return InsertBST(p-lchild,k);elsereturn InsertBST(p-rchild,k);BSTNode *CreateBST(KeyType A, int n) /创建二叉排序树 BSTNode *b

5、t = NULL;int i = 0;while(ikey = k)return bt;if (k key)return SearchBST(bt-lchild, k);elsereturn SearchBST(bt-rchild, k);void charu(BSTNode *&bt)KeyType n;printf(请输入你要插入的元素：);scanf(%d, &n);InsertBST(bt, n);void chazhao(BSTNode *bt)system(cls); /清屏int k;BSTNode *a;printf(请输入要查找的元素：);scanf(%d, &k);a =

6、SearchBST(bt, k);if (a != NULL)printf(找到了元素%dn, k);elseprintf(找不到该元素n);void shuru(BSTNode *&e, int &n)system(cls); /清屏int m, aMax = 0 , i;printf(请输入二叉排序树中元素的个数：n);scanf(%d, &m);n = m;for (i = 0; i lchild);printf(%d , b-key);print1(b-rchild);void print(BSTNode *b)system(cls); /清屏print1(b);int DeleteB

7、ST(BSTNode *&T, int x) /从二叉树排序树T中删除任意结点,其关键字为xBSTNode *p, *q, *pParent, *pChileNode;p = T; /从根结点开始查找pParent = NULL; / T的双亲为NULLwhile (p) / 开始查找关键字为x的结点p,及双亲pParent if (x = p-key)break;pParent = p;p = x p-key ? p-rchild : p-lchild;if (p=NULL)printf(要删除的结点不存在n);return 0; / 至此已找到目标结点p/ pChileNode = p存在

8、的孩子或NULL,左右都存在时，取左pChileNode = p-lchild!= NULL ? p-lchild : p-rchild;if(p-lchild=NULL|p-lchild=NULL)if (pParent = NULL)T= pChileNode;elseif(p=pParent-lchild)pParent-lchild= pChileNode;elsepParent-rchild = pChileNode;free(p); /释放空间 / 当2个孩子都存在时else /pChileNode已指向p-lchildq=p;while (pChileNode-rchild) /

9、在p的左字树中查找中序p的前驱pChileNode，q为其双亲 q=pChileNode;pChileNode = pChileNode-rchild;p-key=pChileNode-key; /p的前驱pChileNodede 的关键值赋给p if(q!=p) /将删除p转化为删除pChileNodede(最多只有左子树)结点 q-rchild=pChileNode-lchild;/p的左子树有右孩子elseq-lchild=pChileNode-lchild; /p的左子树有右孩子free (pChileNode);return 1;void shanchu(BSTNode *&bt)s

10、ystem(cls); /清屏int k, i;printf(请输入你要查找的元素);scanf(%d, &k);i = DeleteBST(bt, k);if (i = 0)printf(删除不成功！n);elseprintf(删除成功！n);void menu()system(cls); /清屏printf(n*菜单*nn);char a50 = 1.输入二叉排序树;char b50 = 2.查找;char c50 = 3.删除;char d50 = 4.插入;char e50 = 5.显示;char f50 = 6.退出;printf(t%-35s%-35snnt%-35s%-35snn

11、t%-35s%-35snn, a, b, c, d, e, f);printf(*n);printf(请选择你要执行的操作对应的序号：n);void main()int n;intaMax = 0;printf(-二叉排序树-nn);printf(t本程序可以实现对一组数据进行查找、插入、删除等操作。nn);BSTNode *e = NULL;for(;)/*无限循环*/printf(按任意键进入主菜单。);getch(); menu(); /*显示菜单*/ /int n;int i=100; /*初始化*/fflush(stdin);/*清空输入缓冲区*/scanf(%d,&i);if(i=0&i=6)switch(i)case 1