二叉排序树的建立及查询[整理版]

二叉排序树的建立及查询[整理版]二叉排序树的建立及查询[整理版] 一、上机实验的问题和要求: 复习二叉排序树的生成及查找算法，编写完整的程序。实现二叉排序树上的查找算法。具体实现要求:用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。二、源程序及注释: #include #include typedef int InfoType; typedef int KeyType; //假定关键字类型为整数 typedef struct node //结点类型 { KeyType key; //关键...

二叉排序树的建立及查询[整理版] 一、上机实验的问题和要求: 复习二叉排序树的生成及查找算法，编写完整的程序。实现二叉排序树上的查找算法。具体实现要求:用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。二、源程序及注释: #include #include typedef int InfoType; typedef int KeyType; //假定关键字类型为整数 typedef struct node //结点类型 { KeyType key; //关键字项 InfoType otherinfo; //其它数据域，InfoType视应用情况而定下面不处理它 struct node *lchild,*rchild;//左右孩子指针 }BSTNode; typedef BSTNode *BSTree; //BSTree是二叉排序树的类型 BSTNode *SearchBST(BSTree T,KeyType key) { //在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL if(T==NULL||key==T->key) //递归的终结条件 return T; //若T为空，查找失败;否则成功，返回找到的结点位置 if(keykey) return SearchBST(T->lchild,key); else return SearchBST(T->rchild,key); //继续在右子树中查找 } void InsertBST(BSTree *T,int key) { //插入一个值为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->key>key) p=q->lchild; else if(p->keyrchild; else { printf("\n该二叉排序树中含有关键字为%d的节点!\n",key); return; } } p=(BSTree)malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; if(q->key>key) q->lchild=p; else q->rchild=p; } } BSTree CreateBST(void) { //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回 BSTree T=NULL; //初始时T为空树 KeyType key; scanf("%d",&key); //读入一个关键字 while(key) { //假设key=0是输入结束标志 InsertBST(&T,key); //将key插入二叉排序树T scanf("%d",&key); //读入下一关键字 } return T; //返回建立的二叉排序树的根指针 } void ListBinTree(BSTree T) //用广义表表示二叉树 { 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(")"); } } } void main() { BSTNode *SearchBST(BSTree T,KeyType key); void InsertBST(BSTree *Tptr,KeyType key); BSTree CreateBST(); void ListBinTree(BSTree T); //用广义表表示二叉树 BSTree T; BSTNode *p; int key; printf("请输入关键字(输入0为结束标志):\n"); T=CreateBST(); ListBinTree(T); printf("\n"); printf("请输入欲查找关键字:"); scanf("%d",&key); p=SearchBST(T,key); if(p==NULL) printf("没有找到%d～\n",key); else printf("找到%d～\n",key); ListBinTree(p); printf("\n"); } 三、运行输出结果: 四、调试和运行程序过程中产生的问题及采取的措施 : 1、输入数据时，总是不能得到结果，原因:在建立二叉树函数定义中，是对指针的值进行了修改; 解决方法:用指向指针的指针。 2、实验中经常会出现前后字符不一致的情况，主要原因是自己在编程时比较马虎，遇到比较长的程序，就容易出错。解决方法:平时应多加练习，要仔细认真检查自己是否出现错误。 3、在类似(*T)->key=key的语句中，括号没加，程序无法运行; 解决方法:加上括号即可。五、思考题: 请思考采用其他存储结构实现的二叉排序树建立算法。用下列程序代替源程序中的相应的部分。 void InsertBST(BSTree *Tptr,KeyType key) { BSTNode *f,*p=*Tptr; while(p) { if(p->key==key) return; f=p; p=(keykey)? p->lchild:p->rchild; } p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; if(*Tptr==NULL) *Tptr=p; else if(keykey) f->lchild=p; else f->rchild=p; } BSTree CreateBST(void) { BSTree T=NULL; KeyType key; scanf("%d",&key); while(key) { InsertBST(&T,key); scanf("%d",&key); } return T; } 六、实验总结 : 在开始编程时，不知道从何入手，自己在上课听讲了，而且也懂了。在编程时想自己独立完成，但看到要求之后突然感觉很迷茫，不得以看得借鉴老师提供的代码。其中有诸多原因，首先自己在编程经验上严重欠缺，这使得自己在接到一道题时无从下手，另外对二叉排序树的理解不够深入，所有编程都是建立在对其算法结构有深入理解的基础上的。而且听懂不意味着理解，只有在自己亲自编程的实践过程中，才能逐渐加深理解。自己C语言的底子不够厚实，今后要加强C语言知识的理论学习，系统地掌握C语言。这样才能给实践提供良好的理论基础。

                    本文档为【二叉排序树的建立及查询[整理版]】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

二叉排序树的建立及查询[整理版]

你可能还喜欢