查找算法--树表查找之二叉排序树

 

      从前面介绍的查找方法我们知道，折半查找较顺序查找速度快，但折半查找要求表中记录必须有序，因为当在已排序的表中找到新记录恰当的位置时，需要移动许多记录以便为新记录腾出位置。有没有哪一种组织记录的方法使得记录的插入与查找都能够很快地完成呢？本篇博客介绍的树表查找就能解决这个问题。

 

二叉排序树(BST 也叫二叉查找树)

 定义：

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

 

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

 

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

 

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

根据BST的性质可以推出，中序遍历该树所得到的是一个递增序列

样式：

即根结点大于左子树，小于等于右子树。

 

二叉排序树生成和结点插入

      二叉排序树生成是从一个空树开始的，每插入一个关键字，就可以调用一次插入方法。所以，先写出二叉排序树的插入方法，要保证插入后满足BST的性质。

定义树结点的结构为：

//结点结构
struct node
{
	int key;//关键字项
	node * lchild;
	node * rchild;
	node()
	{
		lchild=rchild=NULL;
	}
};

  插入函数代码为：

//二叉排序树节点插入
int  Insert(node * &root,int key)
{
	if(root==NULL)
	{
		root=new node;
		root->key=key;
		return 1;//插入成功
	}
	else if(key==root->key)//已经存在
		return 0;//插入失败

	else if(key<root->key)//插到左子树
		return Insert(root->lchild,key);
	else
		return Insert(root->rchild,key);

}

 有了插入代码，生成二叉排序树的代码就简单了：

//二叉排序树创建
void Create(node * &root)
{
	int a[]={8,3,10,1,6,14,4,7,13};//结点数据
	for(int i=0;i<9;i++)
	   Insert(root,a[i]);//节点插入
	
}

 至此我们就生了一棵二叉排序树如下：

需要注意的是数据顺序不同， 生成的二叉排序树可能不同，你可以试试数据

int a[]={3,8,,10,1,6,14,4,7,13};

很明显不一样，我们需要知道构造高度越小的二叉排序树，查找的效率越高

 

二叉排序树查找

生成二叉排序树后，我们来试试查找6这个结点，查找到就返回该结点的指针，否则返回NULL;

代码如下：

//节点查找
node * Search(node * root,int key)
{
	if(root==NULL)
		return NULL;
	if(root->key==key)
		return root;
	if(root->key>key)
		return Search(root->lchild,key);//左子树查找
	else
		return Search(root->rchild,key);//右子树查找
}

  从查找的平均性能来说，二叉排序树和二分查找差不多，但在维护表的有序性上，二叉排序树更有效，因为无需记录，只需修改指针。

 

二叉排序树删除     

       删除结点后，我们还要保证它的BST性质。更不能把它的子结点丢弃。这里我们很容易想到直接删除此结点和其子结点，在循环调用Insert函数把它的子结点插入进去。

    另一种方法就要分四种情况讨论了：

1.若要删除的是叶子结点，直接删除该结点

2.若要删除的结点只有左子树而无右子树，可直接将其左子树的根节点放在被删除的位置

3.若要删除的结点只有右子树而无左子树，可直接将其右子树的根节点放在被删除的位置

4.若要删除的结点有左右子树，可以从其左子树种选择最大的结点或从右子树中选择最小的结点放到被删的结点的位置

根据分析，我们就能写出代码,注意使用引用类型，因为要对树本身进行操作：

int Delete(node * &root,int key)
{
	if(root==NULL)
		return 0;//空树失败
	else
	{
		if(root->key>key)
			return Delete(root->lchild,key);//递归左子树删除

		else if(root->key<key)
			return Delete(root->rchild,key);//递归右子树删除
		
		else//找到了key值的结点
		{
			//删除
			if(root->rchild==NULL&&root->lchild==NULL)//没有左右子树，即叶子结点，直接删除
			{
				node * temp=root;
				root=NULL;
				delete temp;
				
				//2.delete root;能删除叶子结点，但父结点的lchild或rchild没置NULL
			}

			else if(root->rchild==NULL)//没有右子树。
			{
				 node *temp=root;
				 root=root->lchild;
				 delete temp;
			}
			else if(root->lchild==NULL)//没有左子树
			{
				 node *temp=root;
				 root=root->rchild;
				 delete temp;
			}
			//有左右子树
			else
			{
				Delete2(root,root->lchild);//要用引用类型，因为要对树本身操作
				 
			}
			return 1;
		}


	}
}

 

 

void Delete2(node * & root, node * & right)//要用引用类型，因为要对树本身操作
{
	node * temp;
	if(right->rchild!=NULL)//即找到左子树最右下的结点，即左子树最大值,此时的right指向这个最大结点
		Delete2(root,right->rchild);
	else
	{
		root->key=right->key;
		temp=right;
		right=NULL;
		delete temp;
	}
}

 

      

附上源代码地址：https://github.com/longpo/algorithm/tree/master/BST
 

 

评论

1 楼 xcw512 2015-03-30  

有代码不错。