数据结构实验六

洛阳理工学院实验报告系部计算机系班级B130503学号姓名课程名称数据结构实验日期2014.12.11实验名称二叉排序树的创建和查找成绩实验目的：理解二叉排序树的递归定义，掌握二叉排序树的创建、插入、查找基本操作的实现。实验条件：实验内容与算法思想：内容：利用递归算法创建一棵二叉排序树，并在创建的二叉排序树上实现插入、查找等操作。算法思想：1.调用建立二叉排序树的函数；2.输入数据建立二叉排序树；3.调用中序遍历函数输出所建立的二叉排序树序列；4.输入一个数字，调用二叉排序树插入函数将该数字插入到二叉排序树中；5.输入一个数字，调用二叉排序树查找函数，查找二叉排序树中是否含有该数字；运行结果：1.菜单2.建立二叉排序树3.中序输出序列4.插入操作5.查找操作实验总结：一开始在执行插入操作时，输入与子叶相同的数字插入时会失败，在仔细看插入函数时知道了问题所在。原来是在输入数字与二叉排序树中元素比较大小时只考虑到了大于、小于的情况。在将语句elseif(key(*bst)-key)的条件改为小于等于后就可以在二叉排序树中插入与子叶相同的数字了。附：源程序：#includestdio.h#includestdlib.h#includemalloc.h#defineENDKEY-1#defineNULL0#defineOK1typedefstructnode{intkey;structnode*lchild,*rchild;}BSTNode,*BSTree;intInsertBST(BSTree*bst,intkey)//插入函数{BSTrees;if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;returnOK;}elseif(key=(*bst)-key){InsertBST(&((*bst)-lchild),key);returnOK;}elseif(key(*bst)-key){InsertBST(&((*bst)-rchild),key);returnOK;}}voidCreateBST(BSTree*bst){intkey;*bst=NULL;scanf(%d,&key);while(key!=ENDKEY){InsertBST(bst,key);scanf(%d,&key);}}BSTreeSearchBST(BSTreebst,intkey){if(!bst)returnNULL;elseif(bst-key==key)returnbst;//查找成功elseif(bst-keykey)returnSearchBST(bst-lchild,key);elsereturnSearchBST(bst-rchild,key);}voidInOrder(BSTreeroot)//中序遍历{if(root!=NULL){InOrder(root-lchild);printf(%d,root-key);InOrder(root-rchild);}}voidmain(){intk,d,y,m,n,tag;BSTreeT;while(1){tag=1;y=0;printf(***************************************\n);printf(0.建立二叉排序树\n);printf(1.中序输出二叉排序树\n);printf(2.向二叉排序树中插入元素\n);printf(3.查找二叉排序树中元素\n);printf(4.退出\n);printf(***************************************\n);printf(请输入一个数字执行相应操作：\n);scanf(%d,&k);system(CLS);switch(k){case0:printf(请输入序列,建立二叉排序树,以-1结束:\n);CreateBST(&T);printf(建立完成,任意键返回主菜单\n);getch();printf(\n);system(CLS);break;case1:printf(中序遍历二叉排序树,输出序列为:\n);InOrder(T);printf(\n任意键返回主菜单!\n);getch();system(CLS);break;case2:while(tag!=0){printf(请输入要插入元素值:\n);scanf(%d,&m);if(InsertBST(&T,m)==OK){printf(插入成功!\n);printf(插入元素后,中序遍历二叉排序树,输出序列为:\n);InOrder(T);printf(\n);}elseprintf(插入失败!\n);printf(输入0结束操作,输入1继续操作\n);scanf(%d,&tag);system(CLS);}break;case3:while(tag!=0){printf(请输入你要查找的元素:\n);scanf(%d,&n);if(SearchBST(T,n)==0)printf(查找失败!\n);elseprintf(查找成功!查找数字为%d\n,SearchBST(T,n)-key);printf(输入1继续查找,输入0退出查找\n);scanf(%d,&tag);system(CLS);}break;case4:break;}if(k==4)break;}}