[数据结构] 二叉搜索树 (二叉排序树)

二叉搜索树的基本概念

二叉搜索树（ Binary Search Tree ）也称二叉排序树，是一种各节点值之间存在一定次序关系的二叉树。

二叉搜索树的特点

一般情况下，二叉搜索树中所有节点值是不重复的。
对于二叉搜索树中的每个节点：
（1）如果其左子树不为空，那么其左边的节点值都比当前节点值小；
（2）如果其右子树不为空，那么其右边的节点值都比当前的节点值要大。

二叉搜索树的中序遍历结果，就是所有节点值升序排序的结果。

---

二叉搜索树的查找

二叉搜索树查找的基本步骤

根据二叉搜索树的特点，其实二叉搜索树中的查找和二分查找非常相似。从树的根节点出发，当前节点值 val 如果等于目标值 target，那么就直接返回；如果 val 小于目标值 target，那么就要往左边去寻找；如果 val 大于目标值 target，那么就要往右边去寻找。假如最后节点为 NULL，都没有找到等于目标值的节点，那么说明此时的二叉搜索树中不存在这个等与目标值 target 的节点。

我们将使用递归函数来实现这一过程，假设函数名为 SearchBST，则大致步骤为：
（1）节点为空，没有等于目标值的节点 if(!root) return NULL ；
（2）当前节点值小于目标值 if(root->val < target) return SearchBST(root->left) ；
（3）当前节点值大于目标值 if(root->val > target) return SearchBST(root->right) ；
（4）找到该节点 return root 。

二叉搜索树查找图解

（1）

（2）

（3）

（4）

二叉搜索树查找代码

//递归 查找二叉排序树指定元素target
BinaryTree Search_BST(BinaryTree root, Elemtype target){
    if(!root)                                     //最后没有找到root为NULL
        return NULL;          
    if(target > root->val)                        //root值小于target 往其右子树查找
        return Search_BST(root->rightchild, target);
    if(target < root->val)                        //root值大于target 往其左子树查找
        return Search_BST(root->leftchild, target);
    return root;                                  //找到直接返回该节点
}

---

二叉搜索树的插入

二叉搜索树插入的基本步骤

二叉搜索树插入的元素，首先一定是当前二叉搜索树中不存在的元素，如果要插入的元素 val 已经存在于二叉搜索树中，那么就没有插入的必要了。

二叉搜索树插入新元素，同时还需要使整棵树保持二叉搜索树的性质。所以在插入过程中，我们依旧需要用类似于二分查找的形式来实现插入的操作。从树的根节点出发，如果当前节点为空，说明可以插入到这个位置；如果插入元素 val 与当前节点值相等，说明已经存在，直接 return；如果插入元素 val 小于当前节点值，那么递归往左寻找合适的插入位置；如果插入元素 val 大于当前节点值，那么递归往右寻找合适的插入位置。

我们还是用递归函数来实现这个插入的过程，也是创建二叉搜索树的过程。
假定函数名为 InsertBST ，则大致步骤为：
（1）当前节点位置为空，可以插入，创建一个新节点 root = new Node(val) ；
（2）当前节点值与插入元素值相等，直接 return；
（3）插入元素 val 小于当前节点值，则进行 InsertBST(root->left, val) ；
（4）插入元素 val 大于当前节点值，则进行 InsertBST(root->right, val) 。

二叉搜索树插入图解

（1）

（2）

二叉搜索树插入代码

//二叉排序树元素的插入
void Insert_BST(BinaryTree &root, Elemtype val){
    if(!root){                           //若为当前root为空
        BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
        node->val = val;
        node->leftchild = node->rightchild = NULL;
        root = node;
        return;
    } 
    if(root->val == val) 
        return;                          //当前值已经存在 则不插入

/*                       递归写法                        */	 
    if(root->val > val)
        Insert_BST(root->leftchild, val);
    else
        Insert_BST(root->rightchild, val);
}	

---

二叉搜索树的删除

第一类删除的情况

删除节点为叶子结点

基本步骤

由于删除节点为叶子结点，直接置 NULL 即可，删除完之后不会对整棵树满足二叉搜索树性质产生任何影响。

图解

第二类删除的情况

这一类删除的节点的特点为其只有一个子树，另一个子树为空。这种情况往往也是比较方便处理的。

（1）删除节点只有右子树

当删除节点只有右子树时，为了维持二叉搜索树的特点，只需要将删除节点的右子树继承给其父节点就可以，并且做到了将该节点删除。

基本步骤

假定 root 为当前要删除的节点，直接 root = root->right。

图解

（2）删除节点只有左子树

当删除节点只有左子树时，为了维持二叉搜索树的特点，和上一种情况也类似，将左子树继承给其父节点。

基本步骤

假定 root 为当前要删除的节点，直接 root = root->left。

图解

第三类删除的情况

这一类删除的节点同时含有左子树和右子树，此时的处理是比较麻烦的，但是整理好思路就不难。

本质上，我们要找到当前删除的节点的右子树中的节点值最小的节点，也就是右边第一个大于当前删除节点的节点。我们用 s 来指向这个节点，后期我们将其作为代替当前删除的节点。

但是，s 情况的不同也会导致一些处理上的区别。

（1）右子树根节点为右边的最小节点

s 指向的是右子树中的最小的节点，如果右子树的左子树为空，也就是说右子树的根节点即右子树中最小的节点。那么此时 s 就指向这个右子树根节点，然后只需要将删除节点 root 的左子树继承给 s 的 left ，最后将 s 代替删除节点 root 就可以了。这样就可以保持二叉搜索树的性质。

基本步骤

（1）此时 s 就指向 root->right ；
（2）将 root->left 继承给 s->left ；
（3）s 代替删除节点， root = s。

图解

（2）最后一种情况

基本步骤

s 指向的是右子树中的最小的节点，假如右子树的左子树不为空，那么我们首先要先一直向左搜索，直到右子树的最左边，即找到最左边的节点。而且这个最左边的节点一定是没有左子树的，但是可能存在右子树。为了能够顺利的让 s 代替删除节点 root，根据 s 一定是其父节点的左子树的特点，我们需要先将 s 的右子树继承给其父节点 parent，然后此时的 s 就形成一个单独的节点。最后将删除节点 root->left 赋给 s 的左子树，将 root->right 赋给 s 的右子树，将 root = s 完成代替操作。

为了将 s 的右子树继承给其父节点 parent，在右子树中一直往左寻找最左边的节点时，我们需要定义 parent 来记录其父节点。

（1）在删除节点 root 的右子树中一直往左搜索，找到最左边的节点 s ；
（2）将 s 的右子树继承给 parent， parent->left = s->right ；
（3）将 root 的左右子树继承给 s， s->left = root->left, s->right = root->right ；
（4）最后 root = s 。

图解

二叉搜索树删除代码

//二叉排序树元素的删除  
void Delete_BST(BinaryTree &root, Elemtype val){
    BinaryTree t = root, parent = NULL, s = NULL;

    if(!t){  //要删除节点不存在
        puts("要删除的节点不存在");
        return;
    }

    //当前的root为要删除的节点
    if(t->val == val){
        if(!t->leftchild && !t->rightchild){      //要删除的节点是一个叶子结点 直接置NULL
            root = NULL;
        }
        else if(!t->leftchild && t->rightchild){  //要删除的节点只有右子树，将其右子树的根节点代替删除节点
            root = t->rightchild;
        }
        else if(t->leftchild && !t->rightchild){  //要删除的节点只有左子树，将其左子树的根节点代替删除节点
            root = t->leftchild;
        }

        /*  **个人认为最难的地方 采用迭代法**  */
        else{                                     //要删除的节点既有左子树，又有右子树
            s = t->rightchild;                    //记录删除节点的右子树根节点
            //找到右子树中最小的节点
            if(!s->leftchild){                    //如果此时的s没有左儿子，直接把删除节点的左子树变为此时s(删除节点右儿子)的左子树
                s->leftchild = t->leftchild;
            }else{
                while(s->leftchild){              //找到删除节点的右子树中最左边的节点s 即第一个大于删除节点值的节点(后期将其代替删除节点的位置)
                    parent = s;                   //记录代替位置节点的父节点
                    s = s->leftchild;
                }

                parent->leftchild = s->rightchild;//若代替位置节点有右子树，把其右子树继承给父节点(重构删除节点的右子树)
                s->leftchild = t->leftchild;      //删除节点的左子树变为代替节点的左子树
                s->rightchild = t->rightchild;    //删除节点的右子树变为代替节点的右子树
            }

            root = s;                             //最后将当前s代替要删除的节点
        }

        free(t);
    }   
    else if(val > t->val){
        Delete_BST(t->rightchild, val);           //向其右子树寻找要删除的节点
    }
    else if(val < t->val){
        Delete_BST(t->leftchild, val);            //向其左子树寻找要删除的节点
    }
}

---

二叉搜索树的平均查找度

基本概念

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

查找成功情况下的AVL

计算公式

其中 i 表示当前层级，numi 表示第 i 层的节点个数，nodesum 表示整颗二叉搜索树的节点个数。

图解

计算二叉树节点个数代码

//计算二叉树节点的个数
int Nodenum_of_BST(BinaryTree root){
    if(!root)
        return 0;
    return Nodenum_of_BST(root->leftchild) + Nodenum_of_BST(root->rightchild) + 1;
}

查找失败情况下的AVL

计算公式

其中 i 表示当前层级，supplei 表示第 i 层的要补全的节点个数，supplesum 表示整颗二叉搜索树的要补全的总节点个数。

图解

利用层次遍历求补全节点

double sum1 = 0, sum2 = 0;  
//全局变量 sum1 = ∑(各层节点数 × 对应层级), sum2 = ∑(各层补全节点 × (对应层级-1)）
int n0 = 0, n1 = 0;       
//全局变量 分别用于计算每一层叶子节点 和 度数为1的节点
int supplesum = 0;
//全局变量 计算补全的节点总数

//层次遍历 并利用队列计算二叉树每一层的节点个数
void Show_Level_Order(BinaryTree root){
    if(!root)
	return;
    BinaryTree t = NULL;
    int level = 1;

    std::queue<BinaryTree> q;
    q.push(root);
    while(!q.empty()){
        n0 = n1 = 0;
        int n = q.size();
        for(int i = 0; i < n; i++){
            t = q.front();
            q.pop();
            printf("%d ", t->val);

            if(t->leftchild)  q.push(t->leftchild);
            if(t->rightchild)  q.push(t->rightchild);

            if(!t->leftchild && !t->rightchild)  
                n0 ++ ;  //度数为0的节点
            if(!t->leftchild && t->rightchild || t->leftchild && !t->rightchild) 
                n1 ++ ;  //度数为1的节点
        }
        printf("\n");

        sum1 += n * level;               //每一层节点个数*层级
        sum2 += (n0 * 2 + n1) * level;   //每一层下方需补全节点*层级
        supplesum += (n0 * 2 + n1);      //补全的节点个数 

        level++;
    }
}

---

完整程序测试

代码

????????????点击查看代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<vector>
#include<queue>
#include<algorithm>

typedef int Elemtype;
typedef struct BiNode{

	Elemtype val;
	struct BiNode *leftchild, *rightchild;

}BiNode, *BinaryTree;



//递归 查找二叉排序树指定元素target
BinaryTree Search_BST(BinaryTree root, Elemtype target){
	if(!root)                                     //最后没有找到root为NULL
		return NULL;          
	if(target > root->val)                        //root值小于target 往其右子树查找
		return Search_BST(root->rightchild, target);
	if(target < root->val)                        //root值大于target 往其左子树查找
		return Search_BST(root->leftchild, target);
	return root;                                  //找到直接返回该节点
}


//二叉排序树元素的插入
void Insert_BST(BinaryTree &root, Elemtype val){
	if(!root){                           //若为当前root为空
		BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
		node->val = val;
		node->leftchild = node->rightchild = NULL;
		root = node;
		return;
	} 
	if(root->val == val) 
	    return;                          //当前值已经存在 则不插入

/*                       递归写法                        */	 
	if(root->val > val)
	    Insert_BST(root->leftchild, val);
	else
	    Insert_BST(root->rightchild, val);
}	

/*                       迭代写法                        */
/*  
    BinaryTree t = root, inroot = NULL;
	//t为遍历指针   inroot记录要插入位置的父节点
	while(t){
		inroot = t;
		t = (val < t->val) ? t->leftchild : t->rightchild;
	}
	if(val < inroot->val)
	    inroot->leftchild = node;
	else
	    inroot->rightchild = node;  
*/    



//二叉排序树元素的删除  
void Delete_BST(BinaryTree &root, Elemtype val){
	BinaryTree t = root, parent = NULL, s = NULL;

	if(!t){  //要删除节点不存在
        puts("要删除的节点不存在");
	    return;
    }

	//当前的root为要删除的节点
	if(t->val == val){
		if(!t->leftchild && !t->rightchild){      //要删除的节点是一个叶子结点 直接置NULL
			root = NULL;
		}
		else if(!t->leftchild && t->rightchild){  //要删除的节点只有右子树，将其右子树的根节点代替删除节点
            root = t->rightchild;
        }
        else if(t->leftchild && !t->rightchild){  //要删除的节点只有左子树，将其左子树的根节点代替删除节点
        	root = t->leftchild;
        }

        /*  **个人认为最难的地方 采用迭代法**  */
        else{                                     //要删除的节点既有左子树，又有右子树
        	s = t->rightchild;                    //记录删除节点的右子树根节点
        	//找到右子树中最小的节点
        	if(!s->leftchild){                    //如果此时的s没有左儿子，直接把删除节点的左子树变为此时s(删除节点右儿子)的左子树
        		s->leftchild = t->leftchild;
        	}else{
        		while(s->leftchild){              //找到删除节点的右子树中最左边的节点s 即第一个大于删除节点值的节点(后期将其代替删除节点的位置)
        			parent = s;                   //记录代替位置节点的父节点
        			s = s->leftchild;
        		}

        		parent->leftchild = s->rightchild;//若代替位置节点有右子树，把其右子树继承给父节点(重构删除节点的右子树)
        		s->leftchild = t->leftchild;      //删除节点的左子树变为代替节点的左子树
        		s->rightchild = t->rightchild;    //删除节点的右子树变为代替节点的右子树
        	}

        	root = s;                             //最后将当前s代替要删除的节点
        }

        free(t);
	}   
	else if(val > t->val){
		Delete_BST(t->rightchild, val);           //向其右子树寻找要删除的节点
    }
	else if(val < t->val){
		Delete_BST(t->leftchild, val);            //向其左子树寻找要删除的节点
	}
}

/*   二叉排序树删除操作 个人认为最难地方 else情况的递归写法   */
//*******前面部分都一样
/*
else{
	s = Search_BST_Min(t->rightchild);           //找到右子树最小值的节点 即代替删除节点的节点s
	t->rightchild = Delete_BST(t->rightchild, s->val);
	//递归 对删除节点的右子树进行删除要代替节点的操作
	s->leftchild = t->leftchild;
	s->rightchild = t->rightchild;
	root = s;                                    //最后将s代替当前删除的节点
}
*/
//*******后面部分都一样


//二叉排序树的创建
void Create_BST(BinaryTree &root, std::vector<Elemtype> &v){
	for(auto x : v)	Insert_BST(root, x);
}


//中序遍历
void Show_Infix_Order(BinaryTree root){
	if(!root)
		return;
	Show_Infix_Order(root->leftchild);
	printf("%d ", root->val);
	Show_Infix_Order(root->rightchild);
}


//计算二叉树节点的个数
int Nodenum_of_BST(BinaryTree root){
	if(!root)
		return 0;
	return Nodenum_of_BST(root->leftchild) + Nodenum_of_BST(root->rightchild) + 1;
}


//计算二叉树最大深度
int Depth_of_BST(BinaryTree root){
	if(!root)
		return 0;
	return std::max(Depth_of_BST(root->leftchild), Depth_of_BST(root->rightchild)) + 1;
}



double sum1 = 0, sum2 = 0;  
//全局变量 sum1 = ∑(各层节点数 × 对应层级), sum2 = ∑(各层补全节点 × (对应层级-1)）
int n0 = 0, n1 = 0;       
//全局变量 分别用于计算每一层叶子节点 和 度数为1的节点
int supplesum = 0;
//全局变量 计算补全的节点总数

//层次遍历 并利用队列计算二叉树每一层的节点个数
void Show_Level_Order(BinaryTree root){
	if(!root)
		return;
	BinaryTree t = NULL;
	int level = 1;

	std::queue<BinaryTree> q;
	q.push(root);
	while(!q.empty()){
		n0 = n1 = 0;
		int n = q.size();
		for(int i = 0; i < n; i++){
			t = q.front();
			q.pop();
			printf("%d ", t->val);

			if(t->leftchild)  q.push(t->leftchild);
			if(t->rightchild)  q.push(t->rightchild);

			if(!t->leftchild && !t->rightchild)  
				n0 ++ ;  //度数为0的节点
			if(!t->leftchild && t->rightchild || t->leftchild && !t->rightchild) 
				n1 ++ ;  //度数为1的节点
		}
		printf("\n");

		sum1 += n * level;               //每一层节点个数*层级
		sum2 += (n0 * 2 + n1) * level;   //每一层下方需补全节点*层级
		supplesum += (n0 * 2 + n1);      //补全的节点个数 

		level++;
	}
}


//计算二叉排序树的平均查找长度(查找成功的情况)
double ASL_Success(BinaryTree root){
	return double(sum1 / Nodenum_of_BST(root));
}


//计算二叉排序树平均查找长度(查找失败的情况)
double ASL_Fail(BinaryTree root){
	return double(sum2 / supplesum);
}


//递归验证二叉排序树          节点的左右边界
bool IsBST(BinaryTree root, int lower, int upper){
	if(!root)  
		return true;
	if(root->val <= lower || root->val >= upper)  
		return false;
	return IsBST(root->leftchild, lower, root->val) && IsBST(root->rightchild, root->val, upper);
}



int main(){
	BinaryTree T = NULL;
	std::vector<Elemtype> v = {17, 12, 19, 10, 15, 18, 25, 8, 22};
    Create_BST(T, v);
    printf("创建二叉排序树 中序遍历结果: \n");
    Show_Infix_Order(T);
    printf("\n\n");


    printf("验证当前二叉树是否为二叉排序树 \n");
    if(IsBST(T, INT_MIN, INT_MAX))
    	puts("此二叉树为二叉排序树");
    else
    	puts("此二叉树不是二叉排序树");
    printf("\n");


    int e;
    printf("输入要查找的元素: ");
    scanf("%d", &e);
    if(Search_BST(T, e))
    	printf("找到该元素, 其地址为: %d\n", Search_BST(T, e));
    else
    	puts("没有找到该元素");
    printf("\n");


    printf("输入要删除的元素: ");
    scanf("%d", &e);
    Delete_BST(T, e);
    printf("\n进行删除操作后的二叉排序树 层次遍历: \n");
    Show_Level_Order(T);
    printf("\n\n");
   
    printf("当前二叉排序树的最大深度为: %d\n", Depth_of_BST(T));
    printf("\n");

    printf("∑(各层节点数 × 当前层): %d\n", int(sum1));     
    printf("当前二叉搜索树节点个数: %d\n", Nodenum_of_BST(T));
    printf("查找成功的平均查找长度为: %lf\n", ASL_Success(T));
    printf("\n");

    printf("∑(各层补全节点数 × (当前层 - 1)): %d\n", int(sum2));
    printf("当前二叉搜索树需补全的节点个数: %d\n", supplesum);   
    printf("查找失败的平均查找长度为: %lf\n", ASL_Fail(T));
    printf("\n");

    system("pause");
}

测试结果