二叉排序树

二叉排序树 《数据结构》实验四 分校: 湖南城市学院 班级: 1106101 学号: 1106101-24 姓名: 段超 日期: 2012.12.18 程序名: L8. cpp 一、上机实验的问题和要求: 实现二叉排序树上的查找算法。具体实现要求: 1. 用二叉链做存储结构，输入键值序列，建立一棵二叉排序树。 2. 用广义表表示所建二叉树。 3. 按中序遍历这棵二叉排序树。 4. 在二叉排序树上插入结点。 5. 删除二叉排序树上的结点。 6. 在二叉排序树上实现查找算法。 二、程序设计的基本思想，原理和算法描述: (包括程序的结构，数据结构，输入/输出设计，符号名说明等) 基本思想:二叉树的插入和删除同前面基本线性表的插入和删除一样，首先需要找到插入或删除的位置或元素。 基本原理:在一棵非空的二叉树中所有位置都可以插入和删除数据，比较灵活。 算法描述:首先要建立二叉树，按中序遍历二叉树时，若二叉树为空，则不访问任何结点。若二叉树不为空，则中根遍历左子树，访问根结点。中根遍历右子树。 三、源程序及注释: #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是二叉排序树的类型 void main() 1 { void InsertBST(BSTree *Tptr,KeyType key); //将关键字key插入二叉排序树中 BSTree CreateBST(void); //建立二叉排序树 void ListBinTree(BSTree T); //用广义表表示二叉树 void DelBSTNode(BSTree *Tptr,KeyType key); //在二叉排序树中删除关键字key BSTNode *SearchBST(BSTree T,KeyType key); //在二叉排序树中查找关键字key BSTree T; BSTNode *p; int key; printf("请输入关键字(输入0为结束标志):\n"); T=CreateBST(); ListBinTree(T); printf("\n"); printf("请输入欲插入关键字:"); scanf("%d",&key); InsertBST(&T,key); ListBinTree(T); printf("\n"); printf("请输入欲删除关键字:"); scanf("%d",&key); DelBSTNode(&T,key); 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"); } //将关键字key插入二叉排序树中 void InsertBST(BSTree *Tptr,KeyType key) { BSTNode *f,*p=*Tptr; //p的初值指向根结点 while(p){ //查找插入位置 if(p->key==key) return; //树中已有key，无须插入 f=p; //f保存当前查找的结点 p=(keykey)? p->lchild:p->rchild; //若keykey，则在左子树中查找，否则在右子树中查找 } 2 p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; //生成新结点 if(*Tptr==NULL) //原树为空 *Tptr=p; //新插入的结点为新的根 else//原树非空时将新结点*p作为*f的左孩子或右孩子插入 if(keykey) f->lchild=p; else f->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; //返回建立的二叉排序树的根指针 } //在二叉排序树中删除关键字key void DelBSTNode(BSTree *Tptr,KeyType key) { BSTNode *parent=NULL,*p=*Tptr,*q,*child; while(p){ //从根开始查找关键字为key的待删结点 if(p->key==key) break; //已找到，跳出查找循环 parent=p; //parent指向*p的双亲 p=(keykey)?p->lchild:p->rchild;//parent指向*p的左或右子树中继续找 } if(!p) return; //找不到被删结点则返回 q=p; //q记住被删结点*p if(q->lchild && q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p for(parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild); //现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL状况 child=(p->lchild)? p->lchild:p->rchild;//若是情况(2)，则child非空;否则child为空 if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针 *Tptr=child; //若是情况(1)，则删去*p后，树为空;否则child变为根 else { //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下 if(p==parent->lchild) //*p是双亲的左孩子 parent->lchild=child; //*child作为*parent的左孩子 else parent->rchild=child; //*child作为*parent的右孩子 3 if(p!=q) //是情况(3)，需将*p的数据复制到*q q->key=p->key; //若还有其它数据域亦需复制 } free(p); //释放*p占用的空间 } //用广义表表示二叉树 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(")"); } } } //在二叉排序树中查找关键字key BSTNode *SearchBST(BSTree T,KeyType key) { if(T==NULL||key==T->key) //递归的终结条件 return T; //若T为空，查找失败;否则成功，返回找到的结点位置 if(keykey) return SearchBST(T->lchild,key); else return SearchBST(T->rchild,key); //继续在右子树中查找 } }四、运行输出结果: 4 五、调试和运行程序过程中产生的问题及采取的

措施

《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施

: 主要是遇到一些符号和拼写上的错误，少了分号和括号。经过调试还是很好的解决了问题。 六、对算法的程序的讨论、分析，改进设想，其它经验教训: 二叉树的插入和删除与线性表的插入和删除差不多，它是建立在线性表的基础上的。 七、对实验方式、组织、设备、题目的意见和建议: 希望是上机后大家可以交流经验，争取把程序的算法弄得更好些。 5