上机实习题六 查找实验目的掌握查找的不同方法，并能用高级语言实现查找方法。
熟练掌握顺序表和有序表的查找方法以及静态查找树的构造方法和查找算法，理解静态查找树的折半查找方法。
熟练掌握二叉树的构造和查找方法。
而 二、实验内容
设计一个读入一串整数构成的二叉树的算法。
[实现提示] 二叉排序树的构成，可以从空的二叉树开始，每输入一个接点数据，就建立一个新结点、插入都当前已生成的二叉排序树中，所以，它的主要操作是二叉树的插入运算。在儿叉排序数中插入新结点，只要保证插入后仍符合二叉树定义即可。插入是这样进行的：若二叉树为空，则待插入结点*s作为根结点插入到空树；当二叉树非空，将待插结点的关键字s->key与树根的关键字t->key比较，若s->key=t->key,则说明树中以有次结点，无需插入；若s->key<t->key,则将待插结点*s插入到根的左子树，否则将*s插入到根的右子树。而子树的插入过程有和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二插树中，或则直到发现树中已有*s结点为止.
[算法实现]
typedef struct node
{int key;//关键字项
int other;//其他数据项
struct node *lchild,*rchild;
}bstnode;
void inorder (t)//中序遍历二叉树
bstnode *t;
{
if(t!=null)
{inorder(t->lchild);
printf(t->key);
inorder(t->rchild);
}
}
bstnode insertbst(t,s)//将新结点*s插入到t所指的二叉树中
bstnode *s,*t;
{
bstnode *f,*p;
p=t;
while(p!=null)
{
f=p;
if(s->key==p->key)return t;
if(s->key<p->key)p=p->lchild;
else
p=p->rchild;
}
if(t==null)
return s;
if(s->key<f->key)f->lchild=s;
else
f->rchild=s;
return t;
}
bstnode *creatord()//返回二叉树
{
bstnode *t,*s;
int key;
t=null;
scanf(&key);
while(key!=0)
{
s=malloc(sizeof(bitree));
s->key=key;
s->lchild=null;
s->rchild=null;
scanf(&data);
s->other=data;
t=insertbst(t,s);
scanf(&key);
}
return t;
}
main()
{
bstnode *root;
root=creatord();
inorder(root);
}
2.试写出从二叉树中删除一个接点，使该二叉树仍未为叉树的算法。
[实现提示]本题要注意的事，删除二叉树中的结点与删除一棵树中的结点不同，二叉树的结点对应的是一条纪录，只要在删除它后仍使它为二叉排序即可；而要将一棵树中的结点删除，是将该结点同他的左右子树一并删除。
要将二叉树的结点删除，必须建立一棵二叉树，以二叉排序方式表示，然后再进行二叉树结点删除，依据删除结点位置又可分为根和非跟结点两种，可将算法描述为：
若被删除结点k为二叉树的根结点，则:
a:若k有左子树l而无右子树，则将仅需l作为根结点即可
b,若k有右子树r而无左子树，则将仅需r作为根结点即可
c,若k有左子树l而又有右子树r,则将l作为根结点,此时若l无右子树，需将的l右孩子指针指向r；若l有右子树则需沿着l右分支一直往下检索，直到找到最右的且没有右子树的结点为止，即最右下的一个结点，然后把该结点的右孩子指针指向r。
若被删除的结点不是二叉树的根结点，此时可设*p为k的双亲结点，k是*p的左子树活右子树，处理：
a：若k有左子树l，而无右子树，则应将*p结点的左指针或右指针改指向l;
b; 若k无左子树l，而有右子树，则应将*p结点的左指针或右指针改指向r
c,若k有左子树l，又有右子树，则应将*p结点的左指针或右指针改指向l，此时若l无右子树，需将的l右孩子指针指向r；若l有右子树则需沿着l右分支一直往下检索，直到找到最右的且没有右子树的结点为止，即最右下的一个结点，然后把该结点的右孩子指针指向r。
设t为二叉排序树的根指针，而叉排序数一二叉链表储存，k为待删除结点的关键字，则可的程序如下：
[算法实现]首先建立一个二叉树，一二叉链表方式表示
typedef struct node
{ int key; //关键字项
struct node * lchild,*rchild;
}bitree;
void inorder(t)//中序遍历二叉树
bitree *t;
{
if(t!=null)
{
inorder(t->lchild);
printf(t->key);
inorder(t->rchild);
}
}
bitree *inserbst(t,s)// 将新结点*s插入到t所指的二叉树中
{}
bitree *creatord()//返回二叉树
{}
再给出检索算法描述如下：
将p,q作为全程量看待，则有
bstsrch(t,k)//在一个儿叉树t中间所关键字为k的结点
bitree t;//*t 为二叉树的根指针，而叉树以二叉链表存储
int k;
{
int flag;
p=null;//p,q为全程量
q=t;
flag=false;
while((q!=null)&&(flag==false))
if(k==q->key)flag=true;
else
{
p=q;
if(k<q->key)
q=q->lchild;
else
q=q->rchild;
}
}
然后给出删除算法如下：
bittree *p,*q;
bintreedele(t,k)//从二叉树中删除一个结点
bitree *t;
int k;
{
bitree *r;
bstsrch(t,k);//检索过程，、设待删除结点在树中
if(q!=null)// 删除结点在树中
if(p==null)// 删除结点是根结点
if(q->lchild==null)// 删除结点无左子树
t=q->lchild;
else//若被删除得结点无右子树
if(q->rchild==null)
t=q->lchild;
while(r->lchild!=null)
r=r->rchild;//检索中序前驱
r->rchild=q->rchild;
t=q->lchild;
}
else//被删除结点不是根结点
if(q->lchild==null)// 若被删除得结点无左子树
if(q==p->lchild)
p->lchild=q->rchild;
else
{
r=r->rchild;
while(r->rchild!=null)//查找中序前驱
r=r->rchild;
r->rchild=q->rchild;
if(q==p->lchild)
p->lchild=q->lchild;
else
p->rchild=q->lchild;
}
free(q);
}
main()
{bitree *root,*p,*q;
int k;
root=creatord();
inorder(root);
scanf(&k);
bintreedele(root,k);
inorder(root);
}
3.试设计菲薄那检索算法。
[实现提示]菲薄那检索是利用数列fibonacci进行的一种检索的方法首先给出数列如下：
f0=0 n=0
f1=1 n=1
.
.
.
fn=fn-1+fn-2 n>=2;
从而可得菲薄那序列为：0，1，2，3，5，8，13，21，…..假设利用一个数组r来存放菲薄那数列，且r数组中的元素安关键字从大到小的顺序排列，并且假定元素个数n比某个fibonacci数fm小1，即n=fm- 1,第一次，用要检索的关键字key与r[fm-1].key进行比较，其算法思想为：
若key=r[fm-1].key，则检索成功，r[fm-1]为key所在纪录
(2)若key<r[fm-1].key，则下一次检索时再从1到fm-1 -1的范围进行，此时序列长度为fm-1;
若key>r[fm-1].key，则下一次检索在从下标从fm-1 +1到fm -1的范围进行，此时该序列的长度为(fm –1)-(fm-1 +1)+1=fm-fm-1 –1=fm-2 -1，从而可得到：
设r为顺序存储线性表，则：
r[1].key<=r[2].key<=…….<=r[n].key
key为已知关键字，在r中检索关键字为key的纪录，若找到，则返回其下标，否则返回0。假定m为fibonacci数列的序号，则有fm+I=n+1(I>=0,fm+1>I+1,n为记录元素个数)。
[算法实现] 首先可定义一个递归函数，求fibonacci数列的函数
int fibonacci(n)
int n;
{
if(n==0)return(0);
else
if(n==1)return(1);
else
return (fibonacci(n-1)+fibonacci(n-2));}
然后再给出数列检索的算法：
#define keytype int;
#define datatype int;
type struct {
keytype key;
datatype other;
}rectype;
fibonacci(r,k,n)
{
rectype r[];
keytype k;
int n;
{
int I,p,q,t,m,flag;
I=fibonacci(m-1);//设m为 fibonacci数列序号
P=fibonacci(m-2)；
Q=fibonacci(m-3);
S=n+1-(I+p);
If(k>r[I].key I=I+s;
Flag=false;
While((i))&&(!flag))
Switch
{
case k==r[I].key,flag=ture;
break;//检索成功
case k<r[I].key,if(q==0) I=0;//检索失败
else
{I=I-q;
t=p;
p=q;
q=t-q;
}
break;
case k>r[I].key,if(p==1)I=0; //检索失败
else
{
I=I+q;
P=p-q;
q=q-p;
}
break;
default:}
ruturn(i);
}
熟练掌握顺序表和有序表的查找方法以及静态查找树的构造方法和查找算法，理解静态查找树的折半查找方法。
熟练掌握二叉树的构造和查找方法。
而 二、实验内容
设计一个读入一串整数构成的二叉树的算法。
[实现提示] 二叉排序树的构成，可以从空的二叉树开始，每输入一个接点数据，就建立一个新结点、插入都当前已生成的二叉排序树中，所以，它的主要操作是二叉树的插入运算。在儿叉排序数中插入新结点，只要保证插入后仍符合二叉树定义即可。插入是这样进行的：若二叉树为空，则待插入结点*s作为根结点插入到空树；当二叉树非空，将待插结点的关键字s->key与树根的关键字t->key比较，若s->key=t->key,则说明树中以有次结点，无需插入；若s->key<t->key,则将待插结点*s插入到根的左子树，否则将*s插入到根的右子树。而子树的插入过程有和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二插树中，或则直到发现树中已有*s结点为止.
[算法实现]
typedef struct node
{int key;//关键字项
int other;//其他数据项
struct node *lchild,*rchild;
}bstnode;
void inorder (t)//中序遍历二叉树
bstnode *t;
{
if(t!=null)
{inorder(t->lchild);
printf(t->key);
inorder(t->rchild);
}
}
bstnode insertbst(t,s)//将新结点*s插入到t所指的二叉树中
bstnode *s,*t;
{
bstnode *f,*p;
p=t;
while(p!=null)
{
f=p;
if(s->key==p->key)return t;
if(s->key<p->key)p=p->lchild;
else
p=p->rchild;
}
if(t==null)
return s;
if(s->key<f->key)f->lchild=s;
else
f->rchild=s;
return t;
}
bstnode *creatord()//返回二叉树
{
bstnode *t,*s;
int key;
t=null;
scanf(&key);
while(key!=0)
{
s=malloc(sizeof(bitree));
s->key=key;
s->lchild=null;
s->rchild=null;
scanf(&data);
s->other=data;
t=insertbst(t,s);
scanf(&key);
}
return t;
}
main()
{
bstnode *root;
root=creatord();
inorder(root);
}
2.试写出从二叉树中删除一个接点，使该二叉树仍未为叉树的算法。
[实现提示]本题要注意的事，删除二叉树中的结点与删除一棵树中的结点不同，二叉树的结点对应的是一条纪录，只要在删除它后仍使它为二叉排序即可；而要将一棵树中的结点删除，是将该结点同他的左右子树一并删除。
要将二叉树的结点删除，必须建立一棵二叉树，以二叉排序方式表示，然后再进行二叉树结点删除，依据删除结点位置又可分为根和非跟结点两种，可将算法描述为：
若被删除结点k为二叉树的根结点，则:
a:若k有左子树l而无右子树，则将仅需l作为根结点即可
b,若k有右子树r而无左子树，则将仅需r作为根结点即可
c,若k有左子树l而又有右子树r,则将l作为根结点,此时若l无右子树，需将的l右孩子指针指向r；若l有右子树则需沿着l右分支一直往下检索，直到找到最右的且没有右子树的结点为止，即最右下的一个结点，然后把该结点的右孩子指针指向r。
若被删除的结点不是二叉树的根结点，此时可设*p为k的双亲结点，k是*p的左子树活右子树，处理：
a：若k有左子树l，而无右子树，则应将*p结点的左指针或右指针改指向l;
b; 若k无左子树l，而有右子树，则应将*p结点的左指针或右指针改指向r
c,若k有左子树l，又有右子树，则应将*p结点的左指针或右指针改指向l，此时若l无右子树，需将的l右孩子指针指向r；若l有右子树则需沿着l右分支一直往下检索，直到找到最右的且没有右子树的结点为止，即最右下的一个结点，然后把该结点的右孩子指针指向r。
设t为二叉排序树的根指针，而叉排序数一二叉链表储存，k为待删除结点的关键字，则可的程序如下：
[算法实现]首先建立一个二叉树，一二叉链表方式表示
typedef struct node
{ int key; //关键字项
struct node * lchild,*rchild;
}bitree;
void inorder(t)//中序遍历二叉树
bitree *t;
{
if(t!=null)
{
inorder(t->lchild);
printf(t->key);
inorder(t->rchild);
}
}
bitree *inserbst(t,s)// 将新结点*s插入到t所指的二叉树中
{}
bitree *creatord()//返回二叉树
{}
再给出检索算法描述如下：
将p,q作为全程量看待，则有
bstsrch(t,k)//在一个儿叉树t中间所关键字为k的结点
bitree t;//*t 为二叉树的根指针，而叉树以二叉链表存储
int k;
{
int flag;
p=null;//p,q为全程量
q=t;
flag=false;
while((q!=null)&&(flag==false))
if(k==q->key)flag=true;
else
{
p=q;
if(k<q->key)
q=q->lchild;
else
q=q->rchild;
}
}
然后给出删除算法如下：
bittree *p,*q;
bintreedele(t,k)//从二叉树中删除一个结点
bitree *t;
int k;
{
bitree *r;
bstsrch(t,k);//检索过程，、设待删除结点在树中
if(q!=null)// 删除结点在树中
if(p==null)// 删除结点是根结点
if(q->lchild==null)// 删除结点无左子树
t=q->lchild;
else//若被删除得结点无右子树
if(q->rchild==null)
t=q->lchild;
while(r->lchild!=null)
r=r->rchild;//检索中序前驱
r->rchild=q->rchild;
t=q->lchild;
}
else//被删除结点不是根结点
if(q->lchild==null)// 若被删除得结点无左子树
if(q==p->lchild)
p->lchild=q->rchild;
else
{
r=r->rchild;
while(r->rchild!=null)//查找中序前驱
r=r->rchild;
r->rchild=q->rchild;
if(q==p->lchild)
p->lchild=q->lchild;
else
p->rchild=q->lchild;
}
free(q);
}
main()
{bitree *root,*p,*q;
int k;
root=creatord();
inorder(root);
scanf(&k);
bintreedele(root,k);
inorder(root);
}
3.试设计菲薄那检索算法。
[实现提示]菲薄那检索是利用数列fibonacci进行的一种检索的方法首先给出数列如下：
f0=0 n=0
f1=1 n=1
.
.
.
fn=fn-1+fn-2 n>=2;
从而可得菲薄那序列为：0，1，2，3，5，8，13，21，…..假设利用一个数组r来存放菲薄那数列，且r数组中的元素安关键字从大到小的顺序排列，并且假定元素个数n比某个fibonacci数fm小1，即n=fm- 1,第一次，用要检索的关键字key与r[fm-1].key进行比较，其算法思想为：
若key=r[fm-1].key，则检索成功，r[fm-1]为key所在纪录
(2)若key<r[fm-1].key，则下一次检索时再从1到fm-1 -1的范围进行，此时序列长度为fm-1;
若key>r[fm-1].key，则下一次检索在从下标从fm-1 +1到fm -1的范围进行，此时该序列的长度为(fm –1)-(fm-1 +1)+1=fm-fm-1 –1=fm-2 -1，从而可得到：
设r为顺序存储线性表，则：
r[1].key<=r[2].key<=…….<=r[n].key
key为已知关键字，在r中检索关键字为key的纪录，若找到，则返回其下标，否则返回0。假定m为fibonacci数列的序号，则有fm+I=n+1(I>=0,fm+1>I+1,n为记录元素个数)。
[算法实现] 首先可定义一个递归函数，求fibonacci数列的函数
int fibonacci(n)
int n;
{
if(n==0)return(0);
else
if(n==1)return(1);
else
return (fibonacci(n-1)+fibonacci(n-2));}
然后再给出数列检索的算法：
#define keytype int;
#define datatype int;
type struct {
keytype key;
datatype other;
}rectype;
fibonacci(r,k,n)
{
rectype r[];
keytype k;
int n;
{
int I,p,q,t,m,flag;
I=fibonacci(m-1);//设m为 fibonacci数列序号
P=fibonacci(m-2)；
Q=fibonacci(m-3);
S=n+1-(I+p);
If(k>r[I].key I=I+s;
Flag=false;
While((i))&&(!flag))
Switch
{
case k==r[I].key,flag=ture;
break;//检索成功
case k<r[I].key,if(q==0) I=0;//检索失败
else
{I=I-q;
t=p;
p=q;
q=t-q;
}
break;
case k>r[I].key,if(p==1)I=0; //检索失败
else
{
I=I+q;
P=p-q;
q=q-p;
}
break;
default:}
ruturn(i);
}
