binary_sort_tree_search.c

这是一个数据结构当中在二分查找树中进行查找的程序。程序运行正确

#include  <stdio.h>
#include  <stdlib.h>

typedef   struct node{
	int          data;                 //建立二叉排序树的节点类型,为了简单,假设数据域为整型变量
    struct node  *lchild, *rchild;     
}BSTNode, *BSTree;                     //这样定义之后,BSTNode *p;和BSTree p;语句表示的含义相同

//函数InsertBST(T,key)在已有的二叉排序树中插入数据值为key的节点,使插入该节点之后的树仍为二叉排序树
void InsertBST(BSTree *T, int key)
{
	BSTNode *p, *q;
    p = (*T);
    while(p != NULL)
	{
		if(p->data == key)             //进行判断,使新插入的节点的数据域与树中其它节点的数据域不同
		{
			printf("树中已有数据域为%d的节点,不需插入\n",key);
            return ;
		}
        q = p ;
        if (key < q->data)    p = p->lchild ;
	         else             p = p->rchild ;
	}

    p = (BSTNode *)malloc(sizeof(BSTNode));
    p->data = key;                     //对新节点进行初始化
    p->lchild = p->rchild = NULL;   
    
	//将p插入到正确的位置,以使插入节点p之后的树仍为二叉排序树
    if ((*T)==NULL) (*T) = p;          //若是第一个插入的节点,则为二叉排序树的根节点
    else if (key < q->data)   q->lchild = p;
	     else                 q->rchild = p;
}

//函数CreateBST()用来建立一棵二叉排序树
BSTree CreateBST(void)
{
	
	int     data;                      
	BSTree  T = NULL ;                 //初始时,树的根节点为空指针
    
	printf("请输入一个关键字(输入-1时结束输入):\n");  //以输入数据-1表示结束
	scanf("%d",&data);

    while (data != -1)
	{
		InsertBST(&T,data);            //将新输入的数据插入到二排序树中
        printf("请输入下一个关键字(输入-1时结束输入):\n");
        scanf("%d",&data);
	}

    return T;
}

//函数Inorder(T)递归地中序遍历所建立的二叉排序树,以检验所建立的二叉排序树是否正确
//若建立的是一棵正确的二叉排序树,则对其中序遍历所得到的序列是一个递增序列
void InorderBST(BSTree T)
{ 
	if(T != NULL)
	{
		InorderBST(T->lchild);
        printf("%d\t",T->data);
        InorderBST(T->rchild);
	}
}

//函数SearchBST(T,key)是在二叉排序树中进行查找的非递归算法,若查找成功,返回相应的指针,否则返回NULL
BSTree SearchBST(BSTree T, int key)
{ 
	BSTNode *p = T;
    while(p)
	{
		if(p->data == key)
		      return p;
		else if(key < p->data)  p = p->lchild ;
		     else               p = p->rchild ;
	}
   	return NULL ;
}

//函数SearchBST_recursion(T,key)是在二叉排序树中进行查找的递归算法,若查找成功,返回相应的指针,否则返回NULL
BSTree SearchBST_recursion(BSTree T, int key)
{ 
	BSTNode *p = T;
    while(p)
	{
		if(p->data == key)	  return p;
		if(key < p->data)     return(SearchBST_recursion(p->lchild, key));
		if(key > p->data)     return(SearchBST_recursion(p->rchild, key));
	}
   	return NULL ;
}

void  main( )
{
	BSTree  T ;
	BSTNode *p ;
	int     key ;

	printf("建立一棵二叉排序树的二叉链表存储\n");
    T=CreateBST();

    printf("对所建立的二叉树进行中序遍历的序列为:\n");
    InorderBST(T);

	printf("\n输入在要查找的数据:");
	scanf("%d",&key);

    //在叉排序树中,对所要查找的数据分别调用非递归查找算法和递归查找算法,比较查找结果是否一致
	p = SearchBST(T,key);
	printf("\n调用非递归算法查找所得结果:");
	if(p == NULL)
		printf("\t查找失败! 没有找到该数据!\n");
	else
		printf("\t查找成功! 找到了数据%d!\n",p->data);

	p = SearchBST_recursion(T,key);
	printf("\n调用递归算法查找所得结果:");
	if(p == NULL)
		printf("\t查找失败! 没有找到该数据!\n");
	else
		printf("\t查找成功! 找到了数据%d!\n",p->data);
}