查找2

查找

一、目的：

掌握二叉排序树上的基本思想和算法实现，了解其查找方法的时间性能（平均查找长度）分析。

二、要求：

实现二叉排序树查找的算法程序

二叉排序树的定义：或者是一棵空树；或者是具有下列性质的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；

（3）它的左、右子树也分别为二叉排序树。

基本思想：当二叉排序树不空时，首先将给定值K和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。

三、实验内容

1、 设计程序，利用插入算法生成二叉排序树，先序遍历输出二叉排序树。编写二叉排序树的查找算法，输入要查找的关键字，查找成功返回结点的位置，显示成功的信息，否则返回NULL。

2、 调试程序。将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，给出树的先序序列。

四、实验报告要求

1、给出实验输入数据及结果。

2、请画出所得到的二叉排序树。

//=======二叉排序树上的查示例======
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
typedef struct node{ //结点类型
int key; //关键字项
struct node *lchild,*rchild; //左右孩子指针
}BSTNode;
typedef BSTNode *BSTree; //BSTree是二叉排序树的类型
//=========将K插入二叉排序树（BST）中======
void InsertBST(BSTree *Tptr,int k)
{
BSTNode *f,*p=*Tptr; //p的初值指向根结点
while(p){ //查找插入位置
if(p->key==k) return; //树中已有k，无须插入
f=p; //f保存当前查找的结点
p=(kkey)? p->lchild:p->rchild;
//若k小于p->key，则在左子树中查找，否则在右子树中查找。
}
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k; p->lchild=p->rchild=NULL; //生成新结点
if(*Tptr==NULL) //原树为空
*Tptr=p; //新插入的结点为新的根
else //原树不空时
if(kkey) //将新结点*p作为*f的左孩子插入
f->lchild=p;
else //否则，新结点*p作为*f的右孩子插入
f->rchild=p;
}
//==========利用插入算法生成二叉排序树=============
BSTree CreatBST(void) //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回。
{ BSTree T=NULL; //初始时T为空
int k;
scanf("%d",&k); //读入一个关键字
while(k){ //假设K=0是输入结束标志
InsertBST(&T,k); //将k插入二叉排序树T
scanf("%d",&k); //读入下一个关键字
}
return T; //返回建立的二叉排序树的根指针
}
//=========二叉排序树上的查找，成功时返回该结点的位置，否则返回NULL=========
BSTNode *SearchBST(BSTree T,int k)
{
if(T==NULL||k==T->key) //递归终结条件
return T; //若T为空，查找失败；否则成功，返回找到的结点位置
if(kkey) //若k小于T->key在左子树上找；否则在右子树上找。
return SearchBST(T->lchild,k);
else
return SearchBST(T->rchild,k); }
//========先序遍历二叉树=============
void Preorder(BSTree T)
{
if(T) {
printf("%4d",T->key); //访问结点
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//==========主函数============
void main()
{
BSTree root,P; //root为根结点指针
int key;
printf("===Input InsertNode,'0' to end===\n"); //输入要插入的结点，"0"结束插入
root=CreatBST(); //创建二叉排序树
printf("====Output Preorder:====\n");
Preorder(root); //先序遍历输出二叉树的结点
printf("\n===Input Search key:====");
scanf("%d",&key); //输入要查找的关键字
P=SearchBST(root,key); //查找返回结点的位置或NULL
if(P) //P值不为NULL，查找成功；否则失败。
printf("Search Finish !!\n");
else
printf("NO Finish !!\n");
}