二叉搜索树的相关笔记

﹏ヽ暗。殇╰゛Y 2022-12-27 07:17 105阅读 0赞

二叉搜索树

1 二叉搜索树的概念

1.1 二叉搜索树(二叉排序树 二叉查找树)  
根节点值大于其左子树中的所有节点的值  
根节点值小于其右子树中的所有节点的值  
左右子树都是二叉搜索树  
1.2 二叉搜索树的存储结构

typedef * KeyType;
    typedef struct 
    {
        
    	//用来比较结点的大小
    	KeyType key;
    }ElemType;
    //这是二叉树的结点定义
    typedef struct BiTNode
    {
        
    	ElemType data;
    	struct BiTNode *lTree, *rTree;
    }BiTNode, *BiTree;
    //实际上 二叉搜索树本质上 还是 二叉树
    //二叉搜索树 只是 在存储顺序上有特殊约定
    typedef BiTNode BSTNode;
    typedef BiTree BSTree;

2 二叉搜索树的查找  
2.1  
从根节点开始查找  
如果是空树,则查找失败  
若tgt 等于根节点的值, 查找成功  
若tgt 小于根节点, 那么 目标可能在左子树上, 所以 递归查找左子树  
若tgt 大于根节点, 那么 目标可能在右子树上, 所以 递归查找右子树

(如果不存在这个元素的话,最终会 到达叶子结点的子树, 也就是 null)
    (这个操作对空树也满足)

代码实现
    	//查找的元素结点,又不是树,
    	//所以我选择返回结点,但是ppt上返回的是树
    	//根据key值来查找(定位)
    	BSTNode * BSTSearch(BSTree T, KeyType key)
    	{
        
    		if (T == NULL) return NULL;
    		else 
    		{
        
    			if (T->data.key == key) 
    				return T;
    			else if (key < T->data.key)
    				return BSTSearch(T->lTree, key);
    			else if (key > T->data.key)
    				return BSTSearch(T->rTree, key);
    		}
    	}
    	//非递归实现
    	/*
    		p最初指向二叉搜索树的根节点, 只要p不为空且不是目标结点
    		则往下查找
    		如此重复直到 p为空 或者 找到
    	*/
    	BiTNode * BSTSearch(BSTree T, KeyType key)
    	{
        
    		BiTNode *p = T;
    		while (p && p->data.key != key)
    		{
        
    			if (key < T->data.key)
    				p = T->lTree;
    			else if (key > T->data.key)
    				p = T->rTree;
    		}
    		//if (p == NULL) return NULL;
    		//else return p;
    		//上面注释的两行可以写成一行
    		return p;
    	}

3 二叉搜索树的增删  
3.1 插入节点的过程  
先查找是否存在该节点,若不存在, 插入位置在最后走到的结点  
的左右孩子位置插入

Status BSTInsert(BSTree &T, ElemType e)
    {
        
    	if (T == NULL)
    	{
        
    		BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    		if (p == NULL) exit(OVERFLOW);
    		p->data = e;
    		p->lTree = NULL;
    		p->rTree = NULL;
    		/*
    			为什么让 T = p呢?
    			1. 若 原来就是个空树, 那么 这相当于给空树添加了个根节点
    			2. 若遍历到最后一个结点, 此时 T 是 最后一个结点的 左右子树的指针
    			指针存放 左右结点的 地址
    		*/
    		T = p;
    	}
    	else 
    	{
        
    		if (e.key == T->data.key)
    			return ERROR;
    		else if (e.key < T->data.key)
    			BSTInsert(T->lTree, e);
    		else 
    			BSTInsert(T->rTree, e);
    	}
    }

3.2 二叉搜索树的创建

Status CreateBST(BSTree &T)
    {
        
    	T = NULL;
    	InputElem(e);
    	while (! IsEnd(e))
    	{
        
    		//反正我感觉 就算输入有重复 也不能直接退出
    		if (BSTInsert(T, e) == ERROR)
    			return ERROR;
    		//这个 if else关系 没有那么强 
    		else 
    			InputElem(e);
    	}
    }

3.3 删除结点过程  
删除叶子结点: 直接删除  
删除只有一个子树的结点,直接将紫薯接到被删除结点的双亲指针上  
(补充原结点的位置)  
删除有两个子树的结点: 将左子树最大或右子树最小移至 删除位置

定位被删除结点及其 双亲结点, 以便修改在双亲结点上修改孩子的信息

void DeleteBST(BSTree &T, KeyType key)
    {
        
    	p = T;
    	parent_p = NULL;
    	//不能直接调用 BSTSearch, 因为我这个定位过程
    	//涉及到 parent_p 的操作
    	while (p != NULL && key != p->data.key)
    	{
        
    		if (key < T->data.key)
    		{
        
    			f = p;
    			p = p->lTree;
    		}
    		else 
    		{
        
    			f = p;
    			p = p->rTree;
    		}
    	}
    	//若没有这个结点, 可以直接退出函数
    	//相当于已经删除
    	if (p == NULL) return ;
    	
    	//1 若删除的结点 没有孩子:
    	//释放完结点p后, 还需要处理双亲的孩子指针
    	//为什么要处理呢?
    	//为了以后插入结点不会出错
    	//否则 若双亲结点存储了垃圾地址
    	//会被误认为存储了结点
    	//在对 双亲指针处理时:
    	//若删除的是 T的根节点(即parent_p为空, 释放完结点后,T需要赋空)
    	if (p->lTree == NULL && p->rTree == NULL)
    	{
        
    		if (f == NULL)
    		{
        
    			free(p);
    			p = NULL;
    			f = NULL;
    		}
    		else if (f->lTree == p)
    		{
        
    			free(p);
    			p = NULL;
    			f->lTree = NULL;
    		}
    		else if (f->rTree == p)
    		{
        
    			free(p);
    			p = NULL;
    			f->rTree = NULL;
    		}
    	}
    	
    	//删除单子树的结点: 释放结点,双亲指针指向被删结点的子树
    	//若双亲为空时:除释放结点外, T也需要赋空
    	//下面只写了 右子树为空, 左子树不空的情况
    	//左子树空, 右子树不空的代码同理
    	if (p->rTree == NULL)
    	{
        
    		if (f == NULL)
    		{
        
    			T = p->rTree;
    			free(p);
    			p = NULL;
    		}
    		else if (f->lTree == p) 
    		{
        
    			f->lTree = p->rTree;
    			free(p);
    			p = NULL;
    		}
    		else if (f->rTree == p)
    		{
        
    			f->rTree = p->rTree;
    			free(p);
    			p = NULL;
    		}
    	}
    	
    	//删除双子节点: 找左子树最大结点(或右子树最小结点),其值赋予被删结点
    	//释放真正被删结点
    	//需要定位真正被删除结点及其双亲
    	if (p->lTree && p->rTree)
    	{
        
    		BiTNode *q = NULL, *parent_q = NULL;
    		parent_q = p;
    		q = p->lTree;
    		while (q->rTree)
    		{
        
    			parent_q = q;
    			q = q->rTree;
    		}
    		//覆盖
    		p->data = q->data;
    		//删除左子树最大结点
    		//被删结点一定有双亲,
    		//被删结点不一定没有孩子,若果有 那么只有 左子树
    		
    		//特别注意这里的if else判断的含义
    		if (parent_q->rTree == q)
    			f->rTree = q->lTree;
    		else 
    			f->lTree = q->lTree;
    		free(q);
    	}		
    }

4 总结与推广