首页 > 代码库 > BST二叉排序树的查找和删除的完整C代码

BST二叉排序树的查找和删除的完整C代码

二叉排序树的查找算法

假定二叉排序树的根节点指针为root,给定的关键字值为key,则查找算法可描述为:

  1. 置初值:p = root ;

  2. 如果 key = p -> data ,则查找成功,算法结束;

  3. 否则,如果key < p->data ,而且 p 的左子树非空,则将 p 的左子树根送 p ,转步骤 2 ;否则,查找失败,算法结束;

  4. 否则,如果 key > p->data ,而且 p 的右子树非空,则将 p 的右子树根送 p ,转步骤 2 ;否则,查找失败,算法结束。

//BST的递归查找
void SearchBST( BiTree t, Elemtype key )
{
	BiTree p;
	p = t;
	if( p ) {
		if( key == p->data )
			printf("查找成功!\n");
		else if( (key < p->data) && (NULL != p->lchild) )
			SearchBST( p->lchild , key );
		else if( (key > p->data) && (NULL != p->rchild) )
			SearchBST( p->rchild , key );
		else
			printf("无此元素!\n");
	}
}

//BST的迭代查找
void _SearchBST( BiTree t, Elemtype key )
{
	BiTree p;
	p = t;
	while( NULL != p && key != p->data ) {
		if( key < p->data )
			p = p->lchild ;
		else
			p = p->rchild ;
	}

	if( NULL != p )
		printf("查找成功!\n");
	else
		printf("无此元素!\n");
}

二叉排序树上结点的删除算法

假设要删除的结点为 p ,结点 p 的双亲结点为 q ,下面分三种情况讨论:

  1. 若 p 为叶子结点,则可直接将其删除:
    //情况1:结点p的双亲结点为q,且p为叶子结点,则直接将其删除。
    		if( NULL == p->lchild && NULL == p->rchild ) {
    			if( p == q->lchild )
    				q->lchild = NULL;
    			if( p == q->rchild )
    				q->rchild = NULL;
    			free(p);
    			p = NULL;
    		}


  2. 若 p 结点只有左子树,或只有右子树,则可将 p 的左子树或右子树直接改为其双亲结点 q 的左子树或右子树:
    //情况2:结点p的双亲结点为q,且p只有左子树或只有右子树,则可将p的左子树或右子树直接改为其双亲结点q的左子树或右子树。
    		else if( (NULL == p->rchild && NULL != p->lchild) ) {	//p只有左子树
    			if( p == q->lchild )
    				q->lchild = p->lchild ;
    			else if( p == q->rchild )
    				q->rchild = p->lchild ;
    			free(p);
    			p = NULL;
    		}
    		else if( NULL == p->lchild && NULL != p->rchild ) {	//p只有右子树
    			if( p == q->lchild )
    				q->lchild = p->rchild ;
    			if( p == q->rchild )
    				q->rchild = p->rchild ;
    			free(p);
    			p = NULL;
    		}


  3. 若 p 既有左子树,又有右子树。则先保存p 结点的直接前驱(或直接后继)s 的 data  ,然后再从二叉排序树中删除 s ,最后将保存起来的 s 结点的 data 赋值给 p 的 data 。

    该步骤难点在于准确理解 p 结点的直接前驱或直接后继的概念。

    这里的 p 的直接前驱是指BST的中序遍历序列中,紧挨在 p 结点之前一个的结点 s ,在BST中,s 位于 p 结点的左子树的最右下方,用 s 的数据代替 p 的数据,该二叉树依然是一个二叉排序树。
    同理,p 的直接后继是指BST的中序遍历序列中,紧挨在 p 结点之后一个的结点 s , 在BST中, s 位于 p 结点的右子树的最左下方,用 s 的数据代替 p 的数据,该二叉树依然是一个二叉排序树。

    //情况3:结点p的双亲结点为q,且p既有左子树又有右子树。本代码使用直接前驱(也可以直接后继)
    	
    		else if( NULL != p->lchild && NULL != p->rchild ) {
    				BiTree s, sParent; 
    				sParent = p;
    				s = sParent->lchild ;
    				while( NULL != s->rchild )	{	//找到p的直接前驱
    					sParent = s;
    					s = s->rchild ;	
    				}
    				temp = s->data ;	
    				DelBSTNode( t, temp );
    				p->data = http://www.mamicode.com/temp;>

BST查找和删除结点的完整C代码

/* 二叉排序树的查找算法的C代码实现 */
#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;

typedef struct BiTNode{
	Elemtype data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//在给定的BST中插入结点,其数据域为element
void BSTInsert( BiTree *t, Elemtype element )
{
	if( NULL == *t ) {
		(*t) = (BiTree)malloc(sizeof(BiTNode));
		(*t)->data = http://www.mamicode.com/element;>

测试数据以及测试结果

9个元素:5 8 2 1 4 7 9 6 3

生成的BST:

测试结果:

测试通过。

BST二叉排序树的查找和删除的完整C代码