19、数据结构与算法实战:二叉排序树

学习笔记:数据结构与算法(十八):二叉排序树

  • 定义
  • 查找操作
  • 插入操作
  • 删除操作

*
小的数值放在左边,大的放在右边。

定义

二叉排序树:又称为二叉查找树,或者是一棵空树,或者具有以下性质

  • 左子树如果不为空,那么左子树上所有结点的值均小于他的根的值
  • 右子树如果不为空,那么右子树上所有结点的值均大于他的根的值
  • 他的左右子树也分别为二叉排序树(递归)

查找操作

实现代码如下:

//二叉链表结点结构定义
typedef struct BiTNode
{
   
     
	int data;
	struct BiTNode *lchild, *rchild;
}BiTNode. *BiTree;

//递归查找二叉排序树中T是否存在key,指针f指向T的双亲,其初始调用值为NULL。
//若查找成功,p指向该数据元素结点,并返回TRUE
//否则指针p指向查找路径上访问的最后一个结点,返回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
   
     
	if(!T)
	{
   
     
		*p = f;
		return FALSE;
	}
	else if(key == T->data)
	{
   
     
		*p = T ;
		return TRUE;
	}
	else if(key < T->data)
	{
   
     
		return SearchBST(T->lchild, key ,T,p);
	}
	else if(key > T->data)
	{
   
     
		return SearchBST(T->rchild, key ,T,p);
	}
}

插入操作

代码实现

//当二叉排序树T中不存在关键字等于key的数据元素时,插入key并返回True
Status InsertBTS(BiTree *T, int key)
{
   
     
	BiTree p ,s;
	//查找不到key
	if(!SearchBST(*T, key ,NULL,&p))
	{
   
     
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = key;
		s->lchild = s->rchild = NULL;
		
		//注意,p是查找时返回的最后一个结点的位置,也就是最接近s数值的位置
		if(!p)
		{
   
     
			*T = s ;//他自己成为了树
		}
		else if(key < p->data)
		{
   
     
			p->lchild = s; //插入s为左孩子 
		}
		else if(key > p->data)
		{
   
     
			p->rchild = s; //插入s为左孩子 
		}
		return TRUE;
	}
	else
		return FALSE;
}

删除操作

如果要删除叶子结点,那么只需要将叶子删除
如果删除的只有左子树或者右子树,删除后只需要继续接上
但是如果删除的又有左子树又有右子树,比较麻烦。

假如要删除105这个结点
*

Status DeleteBST(BiTree *T, int key)
{
   
     
	if(!*T)
	{
   
     
		return FALSE;
	}
	else
	{
   
     
		if(key == (*T)->data)
		{
   
     
			return Delete(T);
		}
		else if(key < (*T)->data)
		{
   
     
			return DeleteBST(&(*T)->lchild, key);
		}
		else
		{
   
     
			return DeleteBST(&(*T)->rchild, key);
		}
	}
}

Status Delete(BiTree *p)
{
   
     
	BiTree q,s;
	
	if((*p)->lchild == NULL)
	{
   
     
		q = *p;
		*p = (*p)->lchild;
		free(q);
	}
	else if((*p)->rchild == NULL)
	{
   
     
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}
	else
	{
   
     
		q = *p ;
		s = (*p)->lchild;
		//找到p的直接前驱s,也就是左子树的最右子树
		while(s->rchild)
		{
   
     
			q =s;
			s = s->rchild;
		}
		(*p)->data = s->data;//数据替换

		//没有右子树
		if(q != *p)
			q->rchild = s->lchild;
		else
			q->lchild = s->lchild;
		free(s);
	}
}

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: