数据结构之二叉查找树的学习笔记-C++技术网

数据结构之二叉查找树的学习笔记

更新时间：2016-05-21 22:31:22浏览次数：1+次

二叉查找树是数据结构里面很重要的树结构，二叉查找树的树结构很容易看懂，但是，一旦我们利用算法来实现的时候，就没有那么容易了。因此，我们在这里主要利用示例讲算法原理！
定义一个数组，然后在定义要搜寻，删除的结点的元素值。首先呢，我们定义结构体来定义二叉树：

typedef struct Node{
DataType data;
struct Node *lChild,*rChild;
}BiTreeNode,*BiTree;

typedef struct{
keyType key;
}DataType;

我们利用二叉查找结构体的变量的二级指针来传递地址，在二叉查找树中插入元素：

        BiTree T=NULL,p;
	DataType table[]={37,32,35,62,82,95,73,12,5};
	DataType x={73},s={32};//x是要搜寻的结点，s是要删除的结点

	int n=sizeof(table)/sizeof(table[0]);
	for(int i=0; i<n; i++)
	{
		BSTInsert(&T,table[i]);
	}

看看插入函数的实现：

int BSTInsert(BiTree *T,DataType x)
{
	BiTree p,cur,parent=NULL;
	cur=*T;
	while(cur!=NULL)
	{
		if(cur->data.key==x.key)
			return 0;
		parent=cur;//找到前驱结点
		if(x.key<cur->data.key)//如果关键字小于p所指向的结点的值，则在左子树中查找
			cur=cur->lChild;
		else
			cur=cur->rChild;
	}
	p=(BiTree)malloc(sizeof(BiTree)*100);
	if(!p)
		exit(-1);
	p->data=x;
	p->lChild=NULL;
	p->rChild=NULL;
	if(!parent)//如果二叉树为空，则第一结点成为根结点
		*T=p;
	else if(x.key<parent->data.key)
	{
		parent->lChild=p;
	}
	else
		parent->rChild=p;
}

为什么利用二级指针呢？就是利用二级指针来判断二叉查找树，以便插入。什么时候执行while呢？就是我们执行完一次for循环给二叉查找树安插了第一个结点之后，我们就能进入while了。parent结点指针指向某一元素的双亲结点，我们就是利用while来找到双亲结点，该双亲结点就是我们要插入的结点的双亲结点。在这里，尤其注意：

p=(BiTree)malloc(sizeof(BiTree)*100);

在《windows在**.exe中触发了一个断点，其原因可能是堆被损坏，这说明...dll中有bug》一文中，我阐述了这句代码的重要性，如果没有分配足够的内存空间，就会出现那篇文章里的错误！
下面，我们看看删除函数：

void DeleteNode(BiTree *s)//删除结点
{
	BiTree q,x,y;
	if(!(*s)->rChild)//若该结点没有右子树
	{
		q=*s;
		*s=(*s)->lChild;
		free(q);
	}
	else if(!(*s)->lChild)//若该结点没有左子树
	{
		q=*s;
		(*s)=(*s)->rChild;
		free(q);
	}
	else//若该结点既有左结点又有右子树
	{
		x=*s;
		y=(*s)->lChild;
		while(y->rChild)
		{
			x=y;
			y=y->rChild;
		}
		(*s)->data=y->data;
		if(x!=*s)//也就是程序进入了while，要删除的结点下的左子树没有右子树
			x->rChild=y->lChild;
		else
			x->lChild=y->lChild;
		free(y);

	}
}

int BSTDelete(BiTree *T,DataType x)
{
	if(!*T)
		return 0;
	else
	{
		if(x.key==(*T)->data.key)
			DeleteNode(T);
		else if(x.key<(*T)->data.key)
			BSTDelete(&(*T)->lChild, x);
		else
			BSTDelete(&(*T)->rChild, x);
		return 1;
	}
}

在这里，我们主要看看DeleteNode函数，该函数实现的就是删除结点的功能。我们需要为我们所删除的结点考虑三种情况：只有左子树，右子树，既有左子树，右子树。
当只有左子树的时候，就直接将该结点的左子树的元素链接到要删除的元素的位置。只有右子树的时候，也是一样的。那么，要是又有右子树，又有左子树呢？我们先这样分析：在用中序遍历输出二叉排序树的所有的元素的时候，该序列是严格的递增的，而我们的序列是这样的：
5 12 32 35 37 62 73 82 95
假设我们删除32，那么删除后的序列是：
5 12 35 37 62 73 82 95
也就是说，我们删除的32的直接前驱元素！那么，怎么找到前驱元素呢？如果我们删除了这个元素之后，根据二叉查找树的结构特点，我们需要找到该结点的左子树中的最大值，那么怎么做呢？很简单：

x=*s;//定义一个结点x，给它赋值为要查找的结点
y=(*s)->lchild；//在要删除的结点中左子树中查找，因此给y赋值第一个左子树
while(y->rChild)
{
	x=y;
	y=y->rChild;//在y的右子树中查找，直到没有结点了
}

下面看看实现：

完整的程序：

#include "stdio.h"
#include "windows.h"

typedef int keyType;

typedef struct{
	keyType key;
}DataType;

typedef struct Node{
	DataType data;
	struct Node *lChild,*rChild;
}BiTreeNode,*BiTree;

int BSTInsert(BiTree *T,DataType x)
{
	BiTree p,cur,parent=NULL;
	cur=*T;
	while(cur!=NULL)
	{
		if(cur->data.key==x.key)
			return 0;
		parent=cur;//找到前驱结点
		if(x.key<cur->data.key)
			cur=cur->lChild;
		else
			cur=cur->rChild;
	}
	p=(BiTree)malloc(sizeof(BiTree)*100);
	if(!p)
		exit(-1);
	p->data=x;
	p->lChild=NULL;
	p->rChild=NULL;
	if(!parent)
		*T=p;
	else if(x.key<parent->data.key)
	{
		parent->lChild=p;
	}
	else
		parent->rChild=p;
}

void InOrderTraverse(BiTree T)//中序遍历
{
	if(T)
	{
		InOrderTraverse(T->lChild);
		printf("%d  ",T->data.key);
		InOrderTraverse(T->rChild);
	}
}

BiTree BSTSearch(BiTree T,DataType x)//查找结点
{
	BiTree p;
	if(T!=NULL)
	{
		p=T;
		while(p!=NULL)
		{
			if(p->data.key==x.key)
			{
				return p;
			}
			else if(x.key<p->data.key)
				p=p->lChild;
			else
				p=p->rChild;
		}
	}
	return NULL;
}

void DeleteNode(BiTree *s)//删除结点
{
	BiTree q,x,y;
	if(!(*s)->rChild)//若该结点没有右子树
	{
		q=*s;
		*s=(*s)->lChild;
		free(q);
	}
	else if(!(*s)->lChild)//若该结点没有左子树
	{
		q=*s;
		(*s)=(*s)->rChild;
		free(q);
	}
	else//若该结点既有左结点又有右子树
	{
		x=*s;
		y=(*s)->lChild;
		while(y->rChild)
		{
			x=y;
			y=y->rChild;
		}
		(*s)->data=y->data;
		if(x!=*s)
			x->rChild=y->lChild;
		else
			x->lChild=y->lChild;
		free(y);

	}
}

int BSTDelete(BiTree *T,DataType x)
{
	if(!*T)
		return 0;
	else
	{
		if(x.key==(*T)->data.key)
			DeleteNode(T);
		else if(x.key<(*T)->data.key)
			BSTDelete(&(*T)->lChild, x);
		else
			BSTDelete(&(*T)->rChild, x);
		return 1;
	}

}

int main()
{
	BiTree T=NULL,p;
	DataType table[]={37,32,35,62,82,95,73,12,5};
	DataType x={73},s={32};//x是要搜寻的结点，s是要删除的结点

	int n=sizeof(table)/sizeof(table[0]);
	for(int i=0; i<n; i++)
	{
		BSTInsert(&T,table[i]);
	}
	printf("中序遍历的结果:\n");
	InOrderTraverse(T);

	p=BSTSearch(T,x);
	if(p!=NULL)
		printf("\n二叉排序树查找，关键字%d存在\n",x.key);
	else
		printf("查找失败!\n");

	BSTDelete(&T,s);
	printf("输出删除结点的元素值为32后的元素:\n");
	InOrderTraverse(T);
	system("pause");
	return 0;
}