1305120411_何彬_实验报告09.doc

计算机科学与工程学院 《算法与数据结构》实验报告(九) 专业班级 2013网络工程01 实验地点 423机房 学生学号 指导教师 赵卿松 学生姓名 实验时间 实验项目 查找技术综合应用 实验类别 基础性（） 设计性（√） 综合性（） 其它（ ） 实验目的及要求 （1）熟练掌握查找的常用算法； （2）设计和应用查找算法解决比较简单的实际问题 日 期： 2015 年 6 月 13 日 实 验 内 容 实验内容：二叉排序树。 任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。 实验说明： 二叉排序树存储结构如下： 二叉排序树插入算法伪代码如下： 二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下： 实 验 内 容 #includestdio.h #includestdlib.h #includeconio.h #define Max 100 typedef int KeyType; typedef struct node { KeyType key; struct node *lchild, *rchild; } 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(kp-key) return InsertBST(p-lchild,k); else return InsertBST(p-rchild,k); } BSTNode *CreateBST(KeyType A[], int n) //创建二叉排序树 { BSTNode *bt = NULL; int i = 0; while(in) { InsertBST(bt,A[i]); i++; } return bt; } BSTNode *SearchBST(BSTNode *bt, KeyType k) // { if (bt == NULL || bt-key == k) return bt; if (k bt-key) return SearchBST(bt-lchild, k); else return 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 = SearchBST(bt, k); if (a != NULL) printf(找到了元素%d\n, k); else printf(找不到该元素\n); } void shuru(BSTNode *e, int n) { system(cls); //清屏 int m, a[Max] = { 0 }, i; printf(请输入二叉排序树中元素的个数：\n); scanf(%d, m); n = m; for (i = 0; i n; i++) { printf(请输入二叉排序树的第%d个元素的个数：, i + 1); scanf(%d, a[i]); } e = CreateBST(a, n); } void print1(BSTNode *b) { if (b != NULL) { print1(b-lchild); printf(%d , b-key); print1(b-rchild); } } void print(BSTNode *b) { system(cls); //清屏 print1(b); } int DeleteBST(BSTNode