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

技术分享 3年前 (2023-02-10) 0 999+

关注

二叉搜索树

二叉搜索树的基本概念

二叉搜索树（ 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("nn");       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("找到该元素, 其地址为: %dn", Search_BST(T, e));     else     	puts("没有找到该元素");     printf("n");       printf("输入要删除的元素: ");     scanf("%d", &e);     Delete_BST(T, e);     printf("n进行删除操作后的二叉排序树 层次遍历: n");     Show_Level_Order(T);     printf("nn");         printf("当前二叉排序树的最大深度为: %dn", Depth_of_BST(T));     printf("n");      printf("∑(各层节点数 × 当前层): %dn", int(sum1));          printf("当前二叉搜索树节点个数: %dn", Nodenum_of_BST(T));     printf("查找成功的平均查找长度为: %lfn", ASL_Success(T));     printf("n");      printf("∑(各层补全节点数 × (当前层 - 1)): %dn", int(sum2));     printf("当前二叉搜索树需补全的节点个数: %dn", supplesum);        printf("查找失败的平均查找长度为: %lfn", ASL_Fail(T));     printf("n");      system("pause"); }