数据结构实验报告（四） 题目：查找的应用 班级：计算机 1002 班 姓名：岳明轩 学号：20102682 一、 实验内容 二叉排序树的创建和查找 二、 实验目的 掌握查找法的工作原理及应用过程，利用其工作原理完成上述实验题目中的内容。 三、 实验要求 为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真 预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成 老师所布置的实验内容。 四、 设计原理 查找算法递归即可，插入算法也非常简单（大数插右边，小数插左边），无需赘述。虽 然题目未要求，但此处简略说明删除的过程和算法设计： 删除可能会引起整棵树的变化，故分以下三种情况讨论： （设 p 为欲删节点，f 为 p 的双亲节点，p 为 f 的左孩子）  若 p 为叶子节点，即 p->lchild 和 p->rchild 都为空，则只需把 f 的 lchild 清空即可。  若 p 只有一个孩子不为空，则只要令这个子树作为 f 的左子树即可。  若 p 的两个孩子均不为空。则找到 p 的左子树中，最右下的节点 s，另 p 的值等 于 s 的值，再把 s 删去，即可。具体算法见程序清单。 五、 程序清单 BST_Structure.h 1. #include "malloc.h" typedef int Status; struct ElemType { int key; char Name[15]; public: ElemType operator =(ElemType &a) //为 ElemType 重载“=” { } this->key=a.key; strcpy(this->Name,a.Name); return *this; }; struct BSTnode { ElemType data; BSTnode *lchild,*rchild; 

}; typedef BSTnode* BSTree; BST_function.h 2. #include"BST_Structure.h" #include"malloc.h" #include"stdio.h" Status InsertBST(BSTree &T,ElemType e); //Create a BSTree Status CreateBSTree(BSTree &T,ElemType* table,int num) { } T=(BSTree)malloc(sizeof BSTnode); T=NULL; for(int i=0;idata.key) {p=T; return TRUE;} else if (keydata.key) return SearchBST(T->lchild,key,T,p); else return SearchBST(T->rchild,key,T,p); //Insert a node into the BSTree Status InsertBST(BSTree &T,ElemType e) { BSTree p,s; if(!SearchBST(T,e.key,NULL,p)) { s=(BSTree)malloc(sizeof (BSTnode)); s->data=e; s->rchild=NULL; s->lchild=s->rchild; if(!p) T=s; else if (e.keydata.key) p->lchild=s; 

else p->rchild=s; return TRUE; } else return FALSE; } Status Delete(BSTree &p); //Delete a node from BSTree Status DeleteBST(BSTree &T,int key) { } if (!T) return FALSE; else { } if (key==T->data.key) return Delete(T); else if (keydata.key) return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key); Status Delete(BSTree &p) { } BSTree q,s; if(!p->rchild) { } q=p;p=p->lchild; free(q); else if (!p->lchild) q=p;p=p->rchild; free(q); { } else { q=p; s=p->lchild; while (s->rchild) { q=s; s=s->lchild;} p->data=s->data; if (q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; free(s); } return TRUE; Status MiddleOrderShow(BSTree T) { 

if(T) { MiddleOrderShow(T->lchild); printf("%d",T->data.key); printf("%s\n",T->data.Name); MiddleOrderShow(T->rchild); } return TRUE; } 3. 主函数 ///////////////////鄙视从网上下载的//////////////////////////// #include"BST_Function.h" #include"stdio.h" void main() { int id; BSTree T,f,p; int number=9;ElemType* Table; Table=(ElemType*)malloc(number*sizeof(ElemType)); int ID[9]={1,5,2,23,18,9,11,30,20}; char NAME[9][15]={"XiaoMing","XiaoHong","XiaoQiang","LiHua","Sheldon","Leonald","Howard","R aj","Penny"}; for (int i=0;idata.Name); } 六、 实验结果 

七、 遇到的问题及解决办法 1. 由于各函数互有交叉引用，故有些函数需要在定义之前事先声明。 2. ElemType 无法赋值，需要重载运算符“=” 3. 在建立 BSTree 时出现问题，发现在使用 InsertBST 之前，根节点 T 应先设定为 NULL。 4. 开始 ElemType 中 Name 设定为 char*，后来无法通过，因为没有分配空间，改为 char[15]即可。 5. 同样的道理，在主函数中要把 Table 传入函数 CreateBSTree 也要先分配空间再行赋 值。 6. 采用了中序遍历的递归算法显示树，发现 ID 递增显示，证明建立正确。 7. 对于删除算法，本来想在 DeleteBST 中调用 Search 函数，但这样一来，就需要在 Delete 函数中将要删除节点的双亲节点的左右孩子节点指向被删节点的孩子节点。 否则会使树断开。而假如不用 Search 函数而再次使用递归，则只需要把指针 p 指 向孩子节点就可以了。原因如下：使用 Search 函数得到的指针 P 是新建的指针变 量通过 Search 函数指向了要删除节点。这样传入 Delete 函数就会发生以上问题。 而使用递归传入 Delete 函数的指针 p 实际上是上一次递归留下的 T->lchild，即要删 除节点的双亲节点的孩子指针。也就是说，对 p 的改动会直接作用于要删除节点 的孩子指针上。这样问题就解决了。