数据结构实验-二叉排序树应用实验报告

else

p->rchild = s; /* 插入s为右孩子 */ return 1; } else

return 0; /* 树中已有关键字相同的结点，不再插入 */ }

模块3-删除节点

算法如下：

int Delete(BiTree *p) {

BiTree q,s;

if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */ {

q=*p; *p=(*p)->lchild; free(q); }

else if((*p)->lchild==NULL) /* 只需重接它的右子树 */ {

q=*p;

*p=(*p)->rchild; free(q); }

else /* 左右子树均不空 */ {

q=*p;

s=(*p)->lchild;

while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */ {

q=s;

s=s->rchild; }

strcpy((*p)->data,s->data); /* s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */ if(q!=*p)

q->rchild=s->lchild; /* 重接q的右子树 */ else

q->lchild=s->lchild; /* 重接q的左子树 */ free(s); }

return 1; }

模块4-查找待删除节点的位置

算法如下：

int DeleteBST(BiTree *T,char *key) {

if(!*T) /* 不存在关键字等于key的数据元素 */ return 0; else {

if (strcmp(key,(*T)->data)==0) /* 找到关键字等于key的数据元素 */ return Delete(T);

else if (strcmp(key,(*T)->data)<0)

return DeleteBST(&(*T)->lchild,key);/* 若待删除节点大于当前节点，则递归访问其左子树 */ else

return DeleteBST(&(*T)->rchild,key);/* 否则访问右子树 */

} }

模块5-功能函数包括查找、插入和删除

算法如下:

void Gongneng(BiTNode *A)

{// 执行操作需将此树的根节点传入到此函数里面 int k; char a[30],c[30],d[30];

printf(\请选择你的操作：\\n\printf(\查找\\n\printf(\删除\\n\printf(\插入\\n\printf(\输入：\scanf(\switch(k)

{//通过switch语句执行不同的操作 case 1 : system(\ printf(\请输入你要查找的节点：\ scanf(\

Search(A, c); //调用查找函数 break; case 2: system(\ printf(\请输入你要删除的节点：\ scanf(\ if(!DeleteBST(&A,a))

printf(\不存在此节点！\\n\ else {printf(\删除节点成功！\\n\\n删除后树的中序遍历结果如下：\\n\ InOrder(A);} break; case 3: system(\ printf(\请输入要插入的节点：\ scanf(\ if(!InsertBST(&A,d))

printf(\插入失败!要插入的节点已存在!\\n\else {

printf(\插入成功!\\n\\n插入后树的中序遍历结果如下：\\n\ InOrder(A); }

break;

default : printf(\输入数值错误!\\n\ } }

四、调试分析

问题及解决方法：

在编写功能函数时，在参数的传递上出现了问题；无法正确的将根节点传入到功能函数里，导致功能函数无法正常运行；解决方法为：void Gongneng(BiTNode *A)； 时空分析：

由于采用二叉链表的存储结构，所以在插入和删除算法的时间复杂度较低；而对于较多的数据元素形成的树时，查找算法在时间复杂度上不算简便；而存储方面，二叉链表构成的二叉排序树存储较为方便且空间利用率高； 经验体会:

二叉链表存储结构的存储密度较高，使用起来较为方便；而且在处理数据方面，二叉链表存储结构的处理性比较好，尤其是对插入和删除算法；

五、使用说明

第一步：点击运行按钮；

第二步: 输入待输入的域名个数k； 第三步：依次输入k个域名；

第四步：回车，程序跳转至功能界面，根据提示输入想要执行的功能选项序号； 第五步：回车后，针对各功能项有提示药查找、插入或者删除的节点； 第六步： 执行功能后，选择结束运行还是继续操作；

第七步：若选择继续操作，则程序进入功能界面，可继续选择执行的功能； 第八步：循环执行第四到七步；

第九步：可在第六步选择退出程序；

六、测试结果