博客

二叉排序树的一些操作

Note：不会贴图QwQ，为了更好的理解最好是找图片并结合给出的思路和代码，自己动手做做OvO…

二叉排序树的查找：

传入参数：

待查找的BST，关键字，指向双亲的指针f，指向查找结点的指针p

思路：

递归遍历BST

查找成功->指针p指向该元素结点

查找失败->指针p指向该路径上访问的上一个结点

递归出口：1.结点空时停；2.找到时停

二叉排序树的插入

传入参数：

待操作的BST，待插入的关键字

思路：

遍历BST->

找到->返回false表示BST中有该元素

没找到->插入元素

插入元素：

两个结构体指针p，s

s为待插入的结点

p为指向待操作的结点的指针

在这些操作中删除操作相对比较复杂一些，需要考虑的情况比较多，最好是结合图片理解(自己画一个QwQ)…


二叉排序树的删除

考虑情况：

1.删除的结点是叶子结点

2.删除的结点是仅有左(右)子树的结点

3.删除的结点是既存在左子树又存在又子树

1和2可视为同一情况

传入参数：

待操作的BST，删除的关键字key

思路：

递归遍历BST如果找到做删除操作，没找到返回false表示查找失败，BST中没有要删除的元素

删除操作：

两个结构体指针q，s；q用来存放待删除结点的上个结点，s为每次迭代的结点

删除情况1：删除的结点只存在左子树，将他左孩子接上即可

删除情况2：删除的结点只存在右子树，将他右孩子接上即可

删除情况3：删除的结点既存在左子树也存在右子树

用直接前驱替换，或者用直接后继替换

BST的代码

// 二叉树的二叉链表结点结构定义
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
	{
		return SearchBST(T->rchild, key, T, p); // 在右子树继续查找
	}
}

// 当二叉排序树 T 中不存在关键字等于 key 的数据元素时
// 插入 key 并返回 true 否则返回 false

Status InsertBST(BiTree *T, int key)
{
	BiTree p, s;
	if(!SearchBST(*T, key, NULL, &p))
	{
		s = new BiTNode;
		s->data = key;
		s->lchild = s->rchild = NULL;
		
		if(!p)
		{
			*T = s; // 插入s为新的根节点
		}
		else if(key < p->data)
		{
			p->lchild = s;  // 插入s为左孩子
		}
		else
		{
			p->rchild = s;  // 插入s为右孩子
		}
		return false;
	}
	else
		return false;   // 树中已有关键字相同的结点不再插入
}

// 二叉排序树的删除操作
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);
		}
	}
}

// 三种情况
// 1.删除的是叶子结点
// 2.删除的结点仅有右(左)子树
// 3.删除的结点既有左子树又有右子树

Status Delete(BiTree *p)
{
	BiTree q, s;    // q用来存放待删除结点的上一个结点(双亲节点)，s为每次迭代所用到的结点
	
	if((*p)->rchild == NULL)    // 只有左子树
	{
		q = *p;
		*p = (*p)->lchild;  // 将左子树接上
		delete(q);
	}
	else if((*p)->lchild == NULL)   // 只有右子树
	{
		q = *p;
		*p = (*p)->rchild;  // 将右子树接上
		delete(q);
	}
	else    // 要么将直接前驱接上，要么将直接后继接上二者择一
	{
		// 直接前驱替换
		q = *p;
		s = (*p)->lchild;
		
		while(s->rchild)    //s一直寻找左子树中最大的结点，也就是s走到右子树为空时的结点
		{
			q = s;  // q每次指向上一层(双亲)
			s = s->rchild;  // s继续向右走
		}

		(*p)->data = s->data;   // 将左子树中的最大值(直接前驱元素)与*p替换
		
		if(q != *p) // p和q不等的时候将s的左子树接到q的右子树
		{
			q->rchild = s->lchild;
		}
		else    // p和q相同的时候将s的左子树接到q的左子树，因为这是pq相同，相当于将s的左子树接上，替换掉s
		{
			q->lchild = s->lchild;
		}
		
		delete(s);  // 释放掉s是因为s是已经替换后的结点，s结点已无意义
	}
	
	return true;
}

结合自己的一些理解写出来的，如果有不完全或者不对的地方请指出，会改正的OuO