1305120411何彬实验报告09

计算机科学与工程学院算法与数据结构实验报告九专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名实验时间实验项目查找技术综合应用实验类别基础性（）设计性（）综合性（）其它（）实验目的及要求（1）熟练掌握查找的常用算法；（2）设计和应用查找算法解决比较简单的实际问题。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明评阅教师赵卿松计算机科学与工程学院算法与数据结构实验报告2日期2015年6月13日实验内容计算机科学与工程学院算法与数据结构实验报告3实验内容二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明二叉排序树存储结构如下TYPEDEFSTRUCTBITNODE/结点结构STRUCTBITNODELCHILD,RCHILD/左右孩子指针BITNODE,BITREE二叉排序树插入算法伪代码如下1若ROOT是空树，则将结点S作为根结点插入；否则2若SDATAROOTDATA，则把结点S插入到ROOT的左子树中；否则3把结点S插入到ROOT的右子树中。二叉排序树中删除一个结点F的左孩子结点P算法伪代码如下1若结点P是叶子，则直接删除结点P；2若结点P只有左子树，则只需重接P的左子树；若结点P只有右子树，则只需重接P的右子树；3若结点P的左右子树均不空，则31查找结点P的右子树上的最左下结点S以及结点S的双亲结点PAR；32将结点S数据域替换到被删结点P的数据域；33若结点P的右孩子无左子树，则将S的右子树接到PAR的右子树上；否则，将S的右子树接到结点PAR的左子树上；34删除结点S；实验内容计算机科学与工程学院算法与数据结构实验报告4INCLUDEINCLUDEINCLUDEDEFINEMAX100TYPEDEFINTKEYTYPETYPEDEFSTRUCTNODEKEYTYPEKEYSTRUCTNODELCHILD,RCHILDBSTNODEINTINSERTBSTBSTNODEPKEYKPLCHILDPRCHILDNULLRETURN1ELSEIFKPKEYRETURN0ELSEIFKKEY计算机科学与工程学院算法与数据结构实验报告5RETURNINSERTBSTPLCHILD,KELSERETURNINSERTBSTPRCHILD,KBSTNODECREATEBSTKEYTYPEA,INTN/创建二叉排序树BSTNODEBTNULLINTI0WHILEIKEYKRETURNBTIFKKEYRETURNSEARCHBSTBTLCHILD,KELSERETURNSEARCHBSTBTRCHILD,K计算机科学与工程学院算法与数据结构实验报告6VOIDCHARUBSTNODEPRINTF“请输入你要插入的元素“SCANF“D“,INSERTBSTBT,NVOIDCHAZHAOBSTNODEBTSYSTEM“CLS“/清屏INTKBSTNODEAPRINTF“请输入要查找的元素“SCANF“D“,ASEARCHBSTBT,KIFANULLPRINTF“找到了元素DN“,KELSEPRINTF“找不到该元素N“VOIDSHURUBSTNODE/清屏INTM,AMAX0,IPRINTF“请输入二叉排序树中元素的个数N“SCANF“D“,NMFORI0ILCHILDPRINTF“D“,BKEYPRINT1BRCHILDVOIDPRINTBSTNODEB计算机科学与工程学院算法与数据结构实验报告8SYSTEM“CLS“/清屏PRINT1BINTDELETEBSTBSTNODEPT/从根结点开始查找PPARENTNULL/T的双亲为NULLWHILEP/开始查找关键字为X的结点P,及双亲PPARENTIFXPKEYBREAKPPARENTPPXPKEYPRCHILDPLCHILDIFPNULLPRINTF“要删除的结点不存在N“RETURN0/至此已找到目标结点P/PCHILENODEP存在的孩子或NULL,左右都存在时，取左PCHILENODEPLCHILDNULLPLCHILDPRCHILDIFPLCHILDNULL|PLCHILDNULL计算机科学与工程学院算法与数据结构实验报告9IFPPARENTNULLTPCHILENODEELSEIFPPPARENTLCHILDPPARENTLCHILDPCHILENODEELSEPPARENTRCHILDPCHILENODEFREEP/释放空间/当2个孩子都存在时ELSE/PCHILENODE已指向PLCHILDQPWHILEPCHILENODERCHILD/在P的左字树中查找中序P的前驱PCHILENODE，Q为其双亲QPCHILENODEPCHILENODEPCHILENODERCHILDPKEYPCHILENODEKEY/P的前驱PCHILENODEDE的关键值赋给PIFQP/将删除P转化为删除PCHILENODEDE最多只有左子树结点QRCHILDPCHILENODELCHILD/P的左子树有右孩子计算机科学与工程学院算法与数据结构实验报告10ELSEQLCHILDPCHILENODELCHILD/P的左子树有右孩子FREEPCHILENODERETURN1VOIDSHANCHUBSTNODE/清屏INTK,IPRINTF“请输入你要查找的元素“SCANF“D“,IDELETEBSTBT,KIFI0PRINTF“删除不成功N“ELSEPRINTF“删除成功N“VOIDMENUSYSTEM“CLS“/清屏计算机科学与工程学院算法与数据结构实验报告11PRINTF“N菜单NN“CHARA50“1输入二叉排序树“CHARB50“2查找“CHARC50“3删除“CHARD50“4插入“CHARE50“5显示“CHARF50“6退出“PRINTF“T35S35SNNT35S35SNNT35S35SNN“,A,B,C,D,E,FPRINTF“N“PRINTF“请选择你要执行的操作对应的序号N“VOIDMAININTNINTAMAX0PRINTF“二叉排序树NN“PRINTF“T本程序可以实现对一组数据进行查找、插入、删除等操作。NN“BSTNODEENULLFOR/无限循环/计算机科学与工程学院算法与数据结构实验报告12PRINTF“按任意键进入主菜单。“GETCHMENU/显示菜单/INTNINTI100/初始化/FFLUSHSTDIN/清空输入缓冲区/SCANF“D“,IFI0BREAK/输入记录/CASE2CHAZHAOEBREAKCASE3SHANCHUEBREAKCASE4CHARUEBREAKCASE5PRINTEBREAKCASE6E