数据结构系列，二叉排序树的结点删除、重排

亦凉 2023-06-29 10:32 20阅读 0赞

二叉排序树

又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：

1.  若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
2.  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3.  它的左右子树，也分别为二叉排序树。

构造一棵二叉排序树的目的，不是为了排序，而是为了提高查找、插入删除关键字的速度。

二叉树的删除，需要保证一点，不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以需要分几种情况：

1.  如果要删除的结点是叶子结点，可直接删除，对树的其他结点没有影响。
2.  如果要删除的结点，只有左孩子，或者只有右孩子，这个结点被删除后，将它的左孩子，或者右孩子整个移动到删除结点的位置。
3.  如要删除的结点既有左孩子，又有右孩子，这种情况要复杂一些：

首先，我们在其左孩子，右孩子两棵树中，找一个最接近这个结点值的数，用这个数替换要删除的结点；

然后，在一棵二叉排序中，最接近某个结点值的数通常有两个，一个比它大的，一个比它小的，也就是对二叉排序树中序遍历后，得到一个序列，最接近它的两个数，刚好是这个数的前驱和后继。

结点删除的图示；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70 1][]

二叉排序树的结构定义，及代码实现：

#ifndef DATA_STRUCTURE_BINARY_SORT_TREE_CLASS_H
    #define DATA_STRUCTURE_BINARY_SORT_TREE_CLASS_H
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 100 //存储空间初始分配量
    #define MAX_TREE_SIZE 100 //二叉树最大结点树
    
    typedef int Status; //表示函数结果的状态码
    typedef int TreeElemType; //树节点的数据类型，暂定int
    typedef TreeElemType SqBiTree[MAX_TREE_SIZE]; //顺序存储结构数组
    
    typedef struct BiTNode {
        int data;//结点的值
        struct BiTNode *lchild, *rchild;//左右孩子指针
    }BiTNode, *BiTree;
    
    TreeElemType Nil = 0; //表示空元素
    
    Status Delete(BiTree *p);
    #endif

#include "BinarySortTree.h"
    
    #include "iostream"
    #include "cstdlib"
    #include "cmath"
    using namespace std;
    
    #define arrayLength(array) sizeof(array) / sizeof(array[0])
    const int array[11] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 36};
    
    /*
    *二叉排序树的查找，树T中是否存在key
    *指针f指向T的双亲，其初始值为空
    * 若查找成功，指针p返回指向该数据元素结点，放回true
    *否则指针p指向查找路径的最后一个结点，返回false
    */
    Status SearchBST(BiTree T, int key, BiTree father, BiTree *p) {
    	if(!T) {
    		*p = father;
    		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都是指针变量
    	BiTree p, s;
    	if (!(SearchBST(*T, key, NULL, &p))) {
    		s = new BiTNode;
    		s->data = key;
    		s->lchild = s->rchild = NULL;
    		//根据查找函数，如果p为空，意味着这是一棵空树，执行第一次插入
    		if (!p) {
    			*T = s;//s为根结点
    		} else if (key < p->data) {
    			p->lchild = s;//s为左孩子
    		} else {
    			p->rchild = s;//s为右孩子
    		}
    		return TRUE;
    	} else {
    		return FALSE;//已存在指定结点，不再插入
    	}
    }
    
    /*
    * 这里的参数，是一个指针常量，不能通过这个指针常量修改指针指向的常量的内容，
    * 但是指针的指向是可以改变的，就是说这个指针常量还可以指向别的地方。
    */
    Status CreateBST(BiTree *T, const int *p, int lenth) {
    	int i;
    	for (i = 0; i< lenth; p++, i++) {
    		cout << "lenth=" << lenth << ",,,i="<<i <<",v= " << *p <<endl;
    		InsertBST(T, *p);
    	}
    	return OK;
    }
    
    Status visit(BiTree T) {
    	if (NULL != T) {
    		cout << "value=" << T->data << endl;
    	} else {
    		cout << "T is null!" <<endl;
    	}
    	return OK;
    }
    
    void InOrderTraverseBST(BiTree T) {
    	if (NULL == T) {
    		//cout << "T is null!" <<endl;
    		return;
    	} else {
    		InOrderTraverseBST(T->lchild);
    		visit(T);
    		InOrderTraverseBST(T->rchild);
    	}
    }
    
    /*
    * 二叉排序树的删除
    * 若二叉排序中存在结点值等于key的数据元素，则删除该结点，并返回TRUE，否则返回FLASE
    */
    Status DeleteBST(BiTree *T, int key) {
    	if (!*T) {//空树
    		return FALSE;
    	} else {
    		//找到了结点值等于key的数据元素
    		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 (NULL == (*p)->rchild) {
    		//只有左孩子，就用它的左孩子替换要删除的结点
    		q = *p;
    		*p = (*p)->lchild;
    		delete q;
    	} else if (NULL == (*p)->rchild) {
    		//只有右孩子，就用它的右孩子替换要删除的结点
    		q = *p;
    		*p = (*p)->rchild;
    		delete q;		
    	} else {
    		//1,q指向要删除的结点，s指向要删除结点的左孩子。
    		q = *p;
    		s = (*p)->lchild;
    		//2,在左孩子中找最大值，也就是找删除点的前驱
    		while (s->rchild) {
    			q = s;
    			s = s->rchild;
    		}
    		//3,用s替换被删除的结点
    		(*p)->data = s->data;
    		if (q != *p) {
    			//重置q的右子树
    			q->rchild = s->lchild;
    		} else {
    			//重置q的左子树
    			q->lchild = s->lchild;
    		}
    		delete s;
    	}
    
    	return TRUE;
    }
    
    int main() {
    	BiTree T = NULL;
    	CreateBST(&T, array, arrayLength(array));
    	InOrderTraverseBST(T);
    	int deleteNode = 47;
    	DeleteBST(&T, deleteNode);
    	cout << "after delete the node :" << deleteNode << endl;
    	InOrderTraverseBST(T);
    }

/\*output\*/

g++ -g BinarySortTree.cpp -o BsTree  
./BsTree

lenth=11,,,i=0,v= 62
    lenth=11,,,i=1,v= 88
    lenth=11,,,i=2,v= 58
    lenth=11,,,i=3,v= 47
    lenth=11,,,i=4,v= 35
    lenth=11,,,i=5,v= 73
    lenth=11,,,i=6,v= 51
    lenth=11,,,i=7,v= 99
    lenth=11,,,i=8,v= 37
    lenth=11,,,i=9,v= 93
    lenth=11,,,i=10,v= 36
    value=35
    value=36
    value=37
    value=47
    value=51
    value=58
    value=62
    value=73
    value=88
    value=93
    value=99
    after delete the node :47
    value=35
    value=36
    value=37
    value=51
    value=58
    value=62
    value=73
    value=88
    value=93
    value=99

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200111161516243.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200111161537989.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw,size_16,color_FFFFFF,t_70