二叉排序树查找.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;

typedef int KeyType;			//假定关键字类型为整数
typedef struct node				//结点类型
{
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据域，InfoType视应用情况而定 下面不处理它
	struct node *lchild,*rchild;//左右孩子指针
}BSTNode;
typedef BSTNode *BSTree;		//BSTree是二叉排序树的类型

void main()
{
	BSTNode *SearchBST(BSTree T,KeyType key);
	void InsertBST(BSTree *Tptr,KeyType key);
	BSTree CreateBST(void);
	void ListBinTree(BSTree T);		//用广义表表示二叉树
	BSTree T;
	BSTNode *p;
	int key;
	printf("请输入关键字（输入0为结束标志）：\n");
	T=CreateBST();
	ListBinTree(T);
	printf("\n");
	printf("请输入欲查找关键字：");
	scanf("%d",&key);
	p=SearchBST(T,key);
	if(p==NULL)
		printf("没有找到%d！\n",key);
	else
		printf("找到%d！\n",key);
	ListBinTree(p);
	printf("\n");
}

BSTNode *SearchBST(BSTree T,KeyType key)
{	//在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL
	if(T==NULL||key==T->key)	//递归的终结条件
		return T;				//若T为空，查找失败；否则成功，返回找到的结点位置
	if(key<T->key)
		return SearchBST(T->lchild,key);
	else
		return SearchBST(T->rchild,key);	//继续在右子树中查找
}

void InsertBST(BSTree *Tptr,KeyType key)
{	//若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回
	BSTNode *f,*p=*Tptr;			//p的初值指向根结点
	while(p){						//查找插入位置
		if(p->key==key) return;		//树中已有key，无须插入
		f=p;						//f保存当前查找的结点
		p=(key<p->key)? p->lchild:p->rchild;
		//若key<p->key，则在左子树中查找，否则在右子树中查找
	}
	p=(BSTNode *)malloc(sizeof(BSTNode));
	p->key=key;p->lchild=p->rchild=NULL;	//生成新结点
	if(*Tptr==NULL)					//原树为空
		*Tptr=p;					//新插入的结点为新的根
	else//原树非空时将新结点*p作为*f的左孩子或右孩子插入
		if(key<f->key)
			f->lchild=p;
		else f->rchild=p;
}

BSTree CreateBST(void)
{	//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
	BSTree T=NULL;				//初始时T为空树
	KeyType key;
	scanf("%d",&key);			//读入一个关键字
	while(key){					//假设key=0是输入结束标志
		InsertBST(&T,key);		//将key插入二叉排序树T
		scanf("%d",&key);		//读入下一关键字
	}
	return T;					//返回建立的二叉排序树的根指针
}

//用广义表表示二叉树
void ListBinTree(BSTree T)
{
	if (T!=NULL)
	{
		printf("%d",T->key);
		if (T->lchild!=NULL||T->rchild!=NULL)
		{
			printf("(");
			ListBinTree(T->lchild);
			if (T->rchild!=NULL)
				printf(",");
			ListBinTree(T->rchild);
			printf(")");
		}
	}
}