搜索
实验三二叉排序树的建立和查找一、实验目的1．掌握二叉排序树的建立算法2．掌握二叉排序树查找算法。二、实验环境操作系统和C语言系统三、预习要求复习二叉排序树的生成及查找算法，编写完整的程序。四、实验内容实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。五、参考算法#includestdio.h#includestdlib.htypedefintInfoType;typedefintKeyType;/*假定关键字类型为整数*/typedefstructnode/*结点类型*/{KeyTypekey;/*关键字项*/InfoTypeotherinfo;/*其它数据域，InfoType视应用情况而定，下面不处理它*/structnode*lchild,*rchild;/*左右孩子指针*/}BSTNode;typedefBSTNode*BSTree;/*BSTree是二叉排序树的类型*/BSTNode*SearchBST(BSTreeT,KeyTypekey){/*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/if(T==NULL||key==T-key)/*递归的终结条件*/returnT;/*若T为空，查找失败；否则成功，返回找到的结点位置*/if(keyT-key)returnSearchBST(T-lchild,key);elsereturnSearchBST(T-rchild,key);/*继续在右子树中查找*/}voidInsertBST(BSTree*T,intkey){/*插入一个值为key的节点到二叉排序树中*/BSTNode*p,*q;if((*T)==NULL){/*树为空树*/(*T)=(BSTree)malloc(sizeof(BSTNode));(*T)-key=key;(*T)-lchild=(*T)-rchild=NULL;}else{p=(*T);while(p){q=p;if(p-keykey)p=q-lchild;elseif(p-keykey)p=q-rchild;else{printf(\n该二叉排序树中含有关键字为%d的节点!\n,key);return;}}p=(BSTree)malloc(sizeof(BSTNode));p-key=key;p-lchild=p-rchild=NULL;if(q-keykey)q-lchild=p;elseq-rchild=p;}}BSTreeCreateBST(void){/*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/BSTreeT=NULL;/*初始时T为空树*/KeyTypekey;scanf(%d,&key);/*读入一个关键字*/while(key){/*假设key=0是输入结束标志*/InsertBST(&T,key);/*将key插入二叉排序树T*/scanf(%d,&key);/*读入下一关键字*/}returnT;/*返回建立的二叉排序树的根指针*/}voidListBinTree(BSTreeT)/*用广义表示二叉树*/{if(T!=NULL){printf(%d,T-key);if(T-lchild!=NULL||T-rchild!=NULL){printf(();ListBinTree(T-lchild);if(T-rchild!=NULL)printf(,);ListBinTree(T-rchild);printf());}}}voidmain(){BSTNode*SearchBST(BSTreeT,KeyTypekey);voidInsertBST(BSTree*Tptr,KeyTypekey);BSTreeCreateBST();voidListBinTree(BSTreeT);BSTreeT;BSTNode*p;intkey;printf(请输入关键字（输入0为结束标志）：\n);T=CreateBST();ListBinTree(T);printf(\n);printf(请输入欲查找关键字:);scanf(%d,&key);p=SearchBST(T,key);if(p==NULL)printf(没有找到%d！\n,key);elseprintf(找到%d！\n,key);ListBinTree(p);printf(\n);}实验中出现的问题及对问题的解决方案输入数据时，总是不能得到结果，原因是在建立二叉树函数定义中，是对指针的值进行了修改。解决方案：用指向指针的指针。其次，实验中经常会出现前后字符不一致的情况，主要原因是自己在编程时比较马虎，遇到比较长的程序，就容易出错。可以通过评审多加练习，仔细认真检查自己是否出现错误。同时在类似(*T)-key=key的语句中，括号没加，程序无法运行。解决方案同上一条。六、思考题请思考采用其他存储结构实现的二叉排序树建立算法。用下列程序代替源程序中的相应部分。voidInsertBST(BSTree*Tptr,KeyTypekey){BSTBode*f,*p=*Tptr;while(p){if(p-key==key)return;f=p;p=(keyp-key)?p-lchild:p-rchild;}p=(BSTNode*)malloc(sizeof(BSTNode));p-key=key;p-lchild=p-rchild=NULL;if(*Tptr==NULL)*Tptr=pp;elseif(keyf-key)f-lchild=p;elsef-rchild=p;}BSTreeCreateBST(void){BSTreeT=NULL;KeyTypekey;scanf(%d,&key);while(key){InsertBST(&T,key);scanf(%d,&key);}returnT;}七、实验总结在开始编程时，不知道从何入手，自己在上课听讲了，也听懂了。在编程是想自己独立完成，但看到要求之后突然感觉很迷茫，不得已借鉴了老师提供的代码。其中有诸多原因，首先自己在编程经验上严重欠缺，这使得自己在接到一道题时无从下手，另外对二叉排序树的理解不够深入，所以编程都是建立在对其算法结构有深入理解的基础上的。而且听懂不意味着理解，只有在自己亲自编程的时间过程中，才能逐渐加深理解。自己C语言的底子不够厚实，今后要加强C语言知识的理论学习，系统地掌握C语言。这样才能给实践提供良好的理论基础。