二叉排序树的删除图解_二叉排序树的删除_二叉排序树的删除代码(5)

free (s);

}return t;

}

-6-

3.1 中序遍历模块 系统将提示用户输入新添加的数据，输入结束后进行中序遍历

关键代码：

inorderTraverse(node *t) /*中序遍历函数*/

{

if(*t){

if(inorderTraverse(&(*t)->lchild))/*中序遍历根的左子树*/

printf("%d ",(*t)->data); /*输出根结点*/

if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/

}

return(1) ;

}

3.2 删除模块

系统将对用户输入的数进行查找，查找到之后删除此数，并对全部数据进行中序遍历。

关键代码：

node Delete(node t,int key) /*删除函数*/

{

node p=t,q=NULL,s,f;

while(p!=NULL) /*查找要删除的点*/

{

if(p->data==key)

-7-

break;

q=p;if(p->data>key) p=p->lchild;

else

p=p->rchild;

}

if(p==NULL)

return t; /*查找失败*/

if(p->lchild==NULL)/*p指向当前要删除的结点*/

{

if(q==NULL) t=p->rchild; /*q指向要删结点的父母*/else

if(q->lchild==p) q->lchild=p->rchild; /*p为q的左孩子*/else

q->rchild=p->rchild;/*p为q的右孩子*/

free(p);

}

else{/*p的左孩子不为空*/

f=p;

s=p->lchild;

while(s->rchild) /*左拐后向右走到底*/

{

f=s;

s=s->rchild;

-8-

}if(f==p) f->lchild=s->lchild; /*重接f的左子树*/

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

p->data=s->data;

free (s);

}

return t;}

4编码与调试

首先进入VC++6.0，打开工程zjr.dsw，然后进入源程序，也可以不打开工程，直

-9-

接双击zjr文件夹下的

4.1 顺序存储

图7.1.1 打开程序，成功显示提示信息

-10-

图7.1.2 输入数据，以0结束输入，操作成功

图7.1.3 功能1：中序输出数据，操作成功

-11-

图7.1.4 功能2：删除数据，显示提示信息，操作成功

-12-

图7.1.5 删除数据，操作成功

图7.1.6 重复执行程序，操作成功

-13-

4.2 二叉链表存储

图7.2.1打开程序，显示提示信息，操作成功

-14-

图7.2.2功能1：输入数据，进行中序遍历，操作成功

图7.2.3功能2：输入数据，进行删除，操作失败，因为没有此数据，显示 错误信息

-15-

图7.2.4功能2：输入数据，进行中序遍历，操作成功

通过上述测试，本系统实现了二叉树的生成，中序遍历，查找删除功能，能避免数据的输入错误等。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它表示随问题的规模n的增大，算法执行时间的增长率和f（n）的增长率相同）和空间复杂度。遍历二叉树的算法中的基本操作是访问结点，则不论按哪一次次序进行遍历，对含n个结点的二叉树，其时间复杂度都为O（n）。所需空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O（n）。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26533-5.html