bistree.h

数据结构中二叉查找树的C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//二叉查找树头文件，二叉查找树性质为：设x为二叉树的一个结点。如果y是x的左子树
//中的一个结点，则key[y]（y结点的关键域）<=key[x]。如果y是x的右子树中的一个结
//点，则key[y]（y结点的关键域）>=key[x]。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef int status;
typedef int KeyType;//关键域数据类型；
typedef int ElemType;
typedef struct NodeData//结点数据类型；
{
	KeyType key;
	ElemType other;
}NodeData;
typedef struct BiSearchTreeNode
{
	NodeData data;
	struct BiSearchTreeNode *parent;//只有根结点的父指针为空；
	struct BiSearchTreeNode *lChild;
	struct BiSearchTreeNode *rChild;
}BiSTNode,*pBiSTNode;

status InitBiSTree(BiSTNode **tRoot)
{//初始化二叉查找树；
	if(!((*tRoot)=(BiSTNode*)malloc(sizeof(BiSTNode))))
		exit(OVERFLOW);
	(*tRoot)->lChild=NULL;
	(*tRoot)->rChild=NULL;
	(*tRoot)->parent=NULL;
	return OK;
}

status BiSTreeInsert(BiSTNode **tRoot,pBiSTNode node)
{//二叉查找树的插入；
	pBiSTNode y=NULL;
	pBiSTNode x=*tRoot;
	while(x!=NULL)
	{
		y=x;
		if(node->data.key<x->data.key)
			x=x->lChild;
		else
			x=x->rChild;
	}
	node->parent=y;
	if(y->parent==NULL)//要插入的是根结点；
		*tRoot=node;
	else if(node->data.key<y->data.key)
		y->lChild=node;
	else
		y->rChild=node;
	return OK;
}

status InorderBiSTWalk(pBiSTNode tRoot)
{//二叉查找树的中序遍历；
	if(tRoot!=NULL)
	{
		InorderBiSTWalk(tRoot->lChild);
		printf("%d ",tRoot->data.key);
		InorderBiSTWalk(tRoot->rChild);
	}
	return OK;
}

pBiSTNode BiSTSearch(pBiSTNode x,KeyType k)
{//查找二叉查找树的元素；
	if(x==NULL||k==x->data.key)
		return x;
	if(k<x->data.key)
		return BiSTSearch(x->lChild,k);
	else
		return BiSTSearch(x->rChild,k);
}

pBiSTNode BiSTMinimum(pBiSTNode x)
{//返回二叉查找树的最小关键字指针；
	while(x->lChild!=NULL)
		x=x->lChild;
	return x;
}

pBiSTNode BiSTMaximum(pBiSTNode x)
{//返回二叉查找树最大关键字指针；
	while(x->rChild!=NULL)
		x=x->rChild;
	return x;
}

pBiSTNode BiSTSuccessor(pBiSTNode x)
{//返回某结点的后继（中序遍历）；
	pBiSTNode y;
	if(x->rChild!=NULL)
		return BiSTMinimum(x->rChild);
	y=x->parent;
	while(y!=NULL&&x==y->rChild)
	{
		x=y;
		y=y->parent;
	}
	return y;
}

pBiSTNode BiSTDelete(BiSTNode **tRoot,pBiSTNode z)
{//删除结点元素，分三种情况：1.z无孩子；2.z只有一个孩子；3.z有两个孩子；
	pBiSTNode x,y;
	if(z->lChild==NULL||z->rChild==NULL)
		y=z;
	else
		y=BiSTSuccessor(z);
	//以上语句找出要删除的节点y；
	if(y->lChild!=NULL)
		x=y->lChild;
	else
		x=y->rChild;
	//x为y的孩子；
	if(x!=NULL)
		x->parent=y->parent;
	//向上连线；
	if(y->parent==NULL)
		*tRoot=x;
	else if(y==y->parent->lChild)
		y->parent->lChild=x;
	else 
		y->parent->rChild=x;
	//向下连线；
	if(y!=z)
		z->data=y->data;
	return y;
}