Question

数据结构:生成一棵二叉排序树， 实现：1、插入一个元素。 2、查找一个元素。 3、删除一个元素。

分别用递归和非递归算法各编写一遍.

Answer 1

#include <stdio.h>
struct node { int data;
struct node *lchild;
struct node *rchild;
}；
typedef struct node NODE;
（1）递归函数
NODE *search(t, x)
NODE *t;
char x;
{ if (t==NULL)
return(NULL);
else
{ if (t->data==x)
return(t);
if (x<t->data)
return(search(t->lchild));
else
return(search(t->rchild));
}
}
（2）非递归函数 用非递归实现查找，程序同样很简单，但效率比递归程序高的多。
NODE *search(NODE *t, char x)
{ NODE *p;
p=t;
while (p!=NULL)
{ if (p->data==x) return(p); /* 查找成功 */
if (x<p->data)
p=p->lchild;
else
p=p->rchlid;
}
printf(“找不到值为%x的结点！”，x);
return (NULL); /* 查找失败 */
void insert(t, s)
NODE **t, *s
{ if (*t==NULL)
*t=s;
else
{ if (s->data<(*t)->data)
insert(&((*t)->lchild),s);
else if (s->data>(*t)->data)
insert(&((*t)->rchild),s);
else
printf("\n数据%d已在二叉排序树中！", s->data);
}
}
void creat(t)
NODE **t
{ int x;
NODE *s;
printf("\n 输入待排序的数据序列（以-1结束）：");
scanf("%d",&x);
while (x!=-1) /* 以-1结束输入 */
{ s=(NODE *)malloc(sizeof(NODE));
s->data=x;
s->lchild=NULL;
s->rchild=NULL;
insert(t,s); /* 插入到二叉排序树中 */
scanf("%d",&x);
}
}

main( )
{ NODE *root=NULL;
printf("\n 创建一棵二叉排序树！");
creat(&root);
printf("二叉排序树中序序列为：");
midorder(root);
} }
void delete(NODE **t,int x)
{ NODE *f,*p,*r;
p=(*t); /* p指向数据域值为x的结点 */
f=NULL; /* f指向p所指的结点的父结点 */
while (p!=NULL&&p->data!=x) /* 查找数据域值为x的结点 */
if (x<p->data)
{ f=p;
p=p->lchild;
}
else
{ f=p;
p=p->rchild;
}
if (p==NULL)
printf("找不到键值为 %d的结点\n",x);
else if (p->lchild==NULL) /* 被删除结点无左子树 */
{ if (f==NULL)
(*t)=p->rchild; /* 被删除结点为根结点 */
else if (f->lchild==p)
f->lchild=p->rchild; /* 被删除结点为其父结点的左子树*/
else
f->rchild=p->rchild; /* 被删除结点为其父结点的右子树*/
}
else /* 被删除结点有左子树 */
{ r=p->lchild;
while (r->rchild!=NULL) /* 找到最右边的结点 */
r=r->rchild;
r->rchild=p->rchild; /* 把被删除结点的右子树作为r的右子树 */
if (f==NULL)
(*t)=p->lchild; /* 被删除结点为根结点 */
else if (f->lchild==p)
f->lchild=p->lchild; /* 被删除结点为其父结点的左子树*/
else
f->rchild=p->lchild; /* 被删除结点为其父结点的右子树*/
}
free(p)

Answer 2

这个网上就有啊，“香港晨骏药行“。
原装进口 质量保证 假一罚十
详细可咨询客服