二叉排序树（二叉查找树、二叉搜索树）（图解+完整代码）

article/2025/8/25 3:37:03

目录

⚽1.什么是二叉排序树

🏐2.构建二叉排序树

🏀3.二叉排序树的查找操作

🥎4.二叉排序树的删除

🎱5.完整代码

⚽1.什么是二叉排序树

我们直接看它的性质：

  • 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
  • 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
  • 它的左、右树又分为⼆叉排序树

显然，二叉排序树与二叉树一样，也是通过递归的形式定义的。因此，它的操作也都是基于递归的方式。

二叉排序树也叫二叉查找树、二叉搜索树，既然名字都不一般，那它显然和普通的二叉树不同。那到底有什么不同，它的特点或者优点在哪里呢？不妨，我们来构建一棵二叉树。

🏐2.构建二叉排序树

假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树：

  1. 首先，将8作为根节点
  2. 插入3，由于3小于8，作为8的左子树
  3. 插入10，由于10大于8，作为8的右子树
  4. 插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
  5. 插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
  6. 插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
  7. 插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
  8. 插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
  9. 插入13，由于13大于8，进入右子树10，又13大于10，进入右子树14,13小于14，则13为14的左子树

经过以上的逻辑，这棵二叉排序树构建完成。

 

我们可以看出：

  • 只要左子树为空，就把小于父节点的数插入作为左子树
  • 只要右子树为空，就把大于父节点的数插入作为右子树
  • 如果不为空，就一直往下去搜索，直到找到合适的插入位置

 了解了如何构建后，我们不禁要问，这有啥用呀？感觉没啥特别的地方呢？别急！我们马上揭晓！

我们对这棵二叉树进行中序遍历，看看会发生什么？你自己试一试！

没错，这棵二叉树中序遍历结果为：

 根据以上思路，我们其实就可以写出代码了，构建的过程其实就是插入的过程：

void insert(int key)
{//定义一个临时指针 用于移动Node* temp = root;//方便移动 以及 跳出循环Node* prev = NULL;//定位到待插入位置的前一个结点while (temp != NULL){prev = temp;if (key < temp->data){temp = temp->left;}else if(key > temp->data){temp = temp->right;}else{return;}}if (key < prev->data){prev->left = (Node*)malloc(sizeof(Node));prev->left->data = key;prev->left->left = NULL;prev->left->right = NULL;}else{prev->right = (Node*)malloc(sizeof(Node));prev->right->data = key;prev->right->left = NULL;prev->right->right = NULL;}
}

🏀3.二叉排序树的查找操作

它既然也叫二叉查找树，那想必会非常方便我们查找吧！它的操作并不是把中序遍历的结果存入数组，然后在有序数组里查找，而是直接在树上查找。其操作与二分查找非常相似，我们来查找7试一试？（这里要说明以下：在正常的数据结构中，由于数据量很大，所以我们也不知道我们想要的元素在不在里面；同时也不知道每个元素具体是多少，只知道他们的大小关系。我们是在此基础上进行查找）

  1. 首先，访问根节点8
  2. 根据性质，7比8小，所以如果7存在，那应该在8的左子树那边，访问8的左子树
  3. 访问到了3，根据第2步的思想，访问3的右子树
  4. 访问到了6，继续访问6的右子树
  5. 访问到了7，刚好找到啦！

 显然，它的效率会比在无序数组中挨着查找快多了吧！我们直接上代码。

/*查找元素key*/
bool search(Node* root, int key)
{while (root != NULL){if (key == root->data)return true;else if (key < root->data)root = root->left;elseroot = root->right;}return false;
}

🥎4.二叉排序树的删除

那么删除就稍微比查找与插入复杂一点，因为需要分类讨论了。

1.被删除结点为叶子结点

直接从二叉排序中删除即可，不会影响到其他结点。例如删去7：

2.被删除结点D仅有一个孩子

  • 如果只有左孩子，没有右孩子，那么只需要把要删除结点的左孩子连接到要删除结点的父亲结点，然后删除D结点；
  • 如果只有右孩子，没有左孩子，那么只要将要删除结点D的右孩子连接到要删除结点D的父亲结点，然后删除D结点。

以D=14为例：它没有右孩子，只有左孩子。（先把10指向14的右指针移动，去指向13，然后再删除14）

 再以D=10为例，它没有左孩子，只有右孩子。（先把8指向10的右指针移动，去指向14，然后再删除10）

 3.被删除结点左右孩子都在

这种情况就要复杂很多了。但没有关系，依然会讲的很清楚。

我们先假设删除根节点8，看看会发生什么？

我们的目标依然是要保证删除结点8后，再次中序遍历它，仍不改变其升序的排列方式。 那么我们只有用7或者10来替换8原来的位置。

我们先看7来顶替位置

 此时7从叶子结点“升迁”到了根节点（只是刚好要删除的结点为根节点，如果删除3，就替换3的位置）

我们再看10来顶替位置

这时候我们就应该会产生两个问题：

为什么是7或者10来替换8的位置？

显然，7与10是挨着8的，如果用其他元素替换则会打扰其顺序。

那7和10怎么在二叉排序树中找到呢？

  • 显然，7在8左子树的“最右边”，10在8右子树的“最左边”。根据二叉排序树的插入方式，比8小的元素一定在左子树，而我们又要找到比8小的最大的数，这样才能保证他们俩在顺序上是挨着的，所以它又会在8的左子树的最右边。同理也可以找到10.

 根据此方法，我们可以直接给出代码

int delete_node(Node* node, int key)
{if (node == NULL){return -1;}else{if (node->data == key){//当我执行删除操作 需要先定位到删除结点的前一个结点（父节点）Node* tempNode = prev_node(root, node, key);Node* temp = NULL;//如果右子树为空，只需要重新连接结点（包含叶子结点），直接删除if (node->right == NULL){temp = node;node = node->left;/*判断待删除结点是前一个结点的左边还是右边*/if (tempNode->left->data == temp->data){Node* free_node = temp;tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;tempNode->right = node;free(free_node);free_node = NULL;}}else if (node->left == NULL){temp = node;node = node->right;if (tempNode->left->data == temp->data){Node* free_node = temp;tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;/tempNode->right = node;free(free_node);free_node = NULL;}}else//左右子树都不为空{temp = node;/*往左子树 找最大值*/Node* left_max = node;//找最大值的临时指针left_max = left_max->left;//先到左孩子结点while (left_max->right != NULL) {temp = left_max;left_max = left_max->right;}node->data = left_max->data;if (temp != node){temp->right = left_max->left;free(left_max);left_max = NULL;}else{temp->left = left_max->left;free(left_max);left_max = NULL;}}}else if(key < node->data){delete_node(node->left, key);}else if (key > node->data){delete_node(node->right, key);}}
}

🎱5.完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct SortTree {int data;//存放数据的数据域struct SortTree* left;//指针域 左指针struct SortTree* right;//指针域 右指针
}Node;
/*全局变量*/
Node* root;//根节点void Init(int);//初始化操作
void insert(int);//插入操作
void show(Node*);
int delete_node(Node*, int);
Node* prev_node(Node*, Node*, int);
bool search(Node* root, int key);
int main()
{Init(8);insert(4);insert(2);insert(5);insert(10);insert(9);insert(13);show(root);delete_node(root, 8);delete_node(root, 13);printf("\n");show(root);
}/*初始化根节点
int key : 根节点的值
*/
void Init(int key)
{root = (Node*)malloc(sizeof(Node));root->data = key;root->left = NULL;root->right = NULL;
}void insert(int key)
{//定义一个临时指针 用于移动Node* temp = root;//方便移动 以及 跳出循环Node* prev = NULL;//定位到待插入位置的前一个结点while (temp != NULL){prev = temp;if (key < temp->data){temp = temp->left;}else if(key > temp->data){temp = temp->right;}else{return;}}if (key < prev->data){prev->left = (Node*)malloc(sizeof(Node));prev->left->data = key;prev->left->left = NULL;prev->left->right = NULL;}else{prev->right = (Node*)malloc(sizeof(Node));prev->right->data = key;prev->right->left = NULL;prev->right->right = NULL;}
}void show(Node* root)
{if (root == NULL){return;}show(root->left);printf("%d ", root->data);show(root->right);
}
/*查找元素key*/
bool search(Node* root, int key)
{while (root != NULL){if (key == root->data)return true;else if (key < root->data)root = root->left;elseroot = root->right;}return false;
}
int delete_node(Node* node, int key)
{if (node == NULL){return -1;}else{if (node->data == key){//当我执行删除操作 需要先定位到前一个结点Node* tempNode = prev_node(root, node, key);Node* temp = NULL;/*如果右子树为空 只需要重新连接结点叶子的情况也包含进去了 直接删除*/if (node->right == NULL){temp = node;node = node->left;/*为了判断 待删除结点是前一个结点的左边还是右边*/if (tempNode->left->data == temp->data){Node* free_node = temp;//释放用的指针tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;//释放用的指针tempNode->right = node;free(free_node);free_node = NULL;}}else if (node->left == NULL){temp = node;node = node->right;if (tempNode->left->data == temp->data){Node* free_node = temp;//释放用的指针tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;//释放用的指针tempNode->right = node;free(free_node);free_node = NULL;}}else//左右子树都不为空{temp = node;/*往左子树 找最大值*/Node* left_max = node;//找最大值的临时指针left_max = left_max->left;//先到左孩子结点while (left_max->right != NULL) {temp = left_max;left_max = left_max->right;}node->data = left_max->data;if (temp != node){temp->right = left_max->left;free(left_max);left_max = NULL;}else{temp->left = left_max->left;free(left_max);left_max = NULL;}}}else if(key < node->data){delete_node(node->left, key);}else if (key > node->data){delete_node(node->right, key);}}
}
/*定位到待删除节点的前一个结点
Node* root 从根节点开始
Node* node 待删除的结点
int key 待删除数据
*/
Node* prev_node(Node* root, Node* node, int key)
{if (root == NULL || node == root){return node;}else{if (root->left != NULL && root->left->data == key){return root;}else if(root->right != NULL && root->right->data == key){return root;}else if (key < root->data){return prev_node(root->left, node, key);}else{return prev_node(root->right, node, key);}}
}

本结就到这里啦，感谢你的支持！


http://chatgpt.dhexx.cn/article/yjODxGQF.shtml

相关文章

种树：二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

种树：二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

虽然今天不是植树节&#xff0c;但是我今天想种树。 文章目录 树&#xff0c;什么是树&#xff1f;二叉树定义二叉树的创建二叉树的前中后序遍历前序遍历&#xff1a;中序遍历后序遍历已知前序、中序遍历结果&#xff0c;还原二叉树已知后序、中序遍历结果&#xff0c;还原二叉…
阅读更多...
java lrucache_Java LruCache 的使用及原理

java lrucache_Java LruCache 的使用及原理

概述 LRU (Least Recently Used) 的意思就是近期最少使用算法&#xff0c;它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。 在我们日常开发中&#xff0c;UI 界面进行网络图片加载是很正常的一件事情&#xff0c;但是当界面上的图片过于多的时候&#xff0c;不可能每次…
阅读更多...
LruCache和DiskLruCache

LruCache和DiskLruCache

前言 Android中的三级缓存主要就是内存缓存和硬盘缓存。 Lru(least recently used)意为最近最少使用算法&#xff0c;核心思想就是当缓存满时&#xff0c;会优先淘汰最近最少使用的缓存对象。 LruCache的使用 在Android中可以直接使用LruCache&#xff0c;算法原理是&#xff1…
阅读更多...
Android LruCache 缓存

Android LruCache 缓存

使用场景 1、场景一&#xff1a;图片缓存利器。 可以规定缓存大小、有效避免OOM、自动移除队尾不用的图片缓存、避免HashMap各种问题。 2、场景二&#xff1a;通信缓存 从服务端需要获取数据&#xff0c;但是当访问的数据比较大&#xff0c;比较多&#xff0c;并且是重复数…
阅读更多...
Java——LRUCache

Java——LRUCache

概念 简单来说&#xff0c;由于我们的空间是有限的&#xff0c;所以发明了这个数据结构&#xff0c;当我们的空间不够添加新的元素时&#xff0c;就会删除最近最少使用的元素。 其底层逻辑通过哈希表和链表共同实现。哈希表中存储链表的每一个元素&#xff0c;方便进行元素的…
阅读更多...
LruCache缓存

LruCache缓存

Lru算法&#xff1a; Lru 指的是“Least Recently Used-近期最少使用算法”。 1、那么LruCache到底是什么呢&#xff1f; LruCache 是对限定数量的缓存对象持有强引用的缓存&#xff0c;每一次缓存对象被访问&#xff0c;都会被移动到队列的头部。当有对象要被添加到已经达到数…
阅读更多...
LruCache 源码解析

LruCache 源码解析

1. 概述 对于 Android 开发者&#xff0c;LruCache 肯定不陌生&#xff0c;几乎所有的图片缓存框架都会用到它来实现内存缓存等&#xff0c;可见 LruCache 在 Android 开发中的重要性。LRU 是 Least Recently Used 的缩写&#xff0c;近期最少使用的意思。当我们进行缓存的时候…
阅读更多...
LruCache

LruCache

LruCache这个类是通过Glide得知的&#xff0c;不过它是自己又基于LRU算法自己写了个LruCache工具类&#xff0c;不过基本原理类似&#xff0c;都是基于LRU算法实现的 1.来源 一般来说&#xff0c;缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比…
阅读更多...
Android基础-LruCache原理解析

Android基础-LruCache原理解析

一、Android中的缓存策略 一般来说&#xff0c;缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比较好理解&#xff0c;那么为什么还要删除缓存呢&#xff1f;这是因为不管是内存缓存还是硬盘缓存&#xff0c;它们的缓存大小都是有限的。当缓存满了…
阅读更多...
LRUCache详解

LRUCache详解

1.概念 LRU是Least Recently Used的缩写&#xff0c;意思是最近最少使用&#xff0c;它是一种Cache替换算法。 Cache的容量有限&#xff0c;因此当Cache的容量用完后&#xff0c;而又有新的内容需要添加进来时&#xff0c; 就需要挑选并舍弃原有的部分内容&#xff0c;从而腾出…
阅读更多...
LRUCache 详解

LRUCache 详解

LRU算法详解 一、什么是 LRU 算法 就是一种缓存淘汰策略。 计算机的缓存容量有限&#xff0c;如果缓存满了就要删除一些内容&#xff0c;给新内容腾位置。但问题是&#xff0c;删除哪些内容呢&#xff1f;我们肯定希望删掉哪些没什么用的缓存&#xff0c;而把有用的数据继续…
阅读更多...
LRU Cache

LRU Cache

前言 哈喽&#xff0c;各位小伙伴大家好&#xff0c;本章内容为大家介绍计算机当中为了提高数据相互传输时的效率而引进的一种重要设计结构叫做LRU Cache,下面将为大家详细介绍什么是LRU Cache,以及它是如何是实现的&#xff0c;如何提升效率的。 1.什么是LRU Cache? LRU是L…
阅读更多...
uniapp日历原生插件

uniapp日历原生插件

<template><!-- 打卡日历页面 --><view classall><view class"bar"><!-- 上一个月 --><view class"previous" click"handleCalendar(0)"><button class"barbtn">上一月</button><…
阅读更多...
微信小程序使用日历插件

微信小程序使用日历插件

一&#xff0c;添加插件 1&#xff0c;在你的小程序关联的微信公众平台打开 设置》第三方服务》添加插件 2&#xff0c;直接AppID&#xff08;wx92c68dae5a8bb046&#xff09;搜索到该插件并申请授权&#xff0c;授权成功即可在小程序使用 二&#xff0c;小程序使用插件 app…
阅读更多...
日历组件

日历组件

日历组件&#xff1a; <template><div class"calendar" click.stop><div class"input-wrap"><inputtype"text"v-if"dateChangeSets":placeholder"placeholder"class"input dateChangeSets middle…
阅读更多...
vue-calendar基于vue的日历插件

vue-calendar基于vue的日历插件

本文转载于https://www.cnblogs.com/zwhgithub/p/8005414.html vue-calendar-component 基于 vue 2.0 开发的轻量&#xff0c;高性能日历组件占用内存小&#xff0c;性能好&#xff0c;样式好看&#xff0c;可扩展性强原生 js 开发&#xff0c;没引入第三方库 效果 Install …
阅读更多...
实用插件（一）日历插件——My97DatePicker

实用插件（一）日历插件——My97DatePicker

注&#xff1a;My97DatePicker插件仅限pc端使用&#xff0c;若是app项目&#xff0c;建议使用ICalendar或者Mobiscroll。 &#xff08;ICalendar插件在华为手机上存在兼容性问题&#xff0c;日期不能滚动&#xff0c;但使用很简单&#xff1b;Mobiscroll使用起来较为复杂&…
阅读更多...
sys-calendar.js带节假日的日历插件

sys-calendar.js带节假日的日历插件

下载地址 sys-calendar.js带节假日的日历插件&#xff0c;代码引用比较多。 dd:
阅读更多...
jquery日历插件，可自定义日期内容

jquery日历插件，可自定义日期内容

效果图&#xff1a; 使用&#xff1a; <link href"static/css/raoCalendar.css" rel"stylesheet" type"text/css"><script src"static/js/jquery.min.js"></script> <script src"static/js/raoCalendar.js…
阅读更多...
两款超好用js日历插件（fullcalendar和zabuto_calendar）

两款超好用js日历插件（fullcalendar和zabuto_calendar）

这两款插件特别类似，其实用其中一款即可。 先展示一下我用这两款插件制作的排班系统 这个是fullcalendar插件制作的排班页面，左边新建一系列组和组员，可以将人员直接拖拽至右边的日历上，不同组以颜色区别。 这个是将上面的排班内容用zabuto_calendar插件显示出来，黄色区域…
阅读更多...
推荐文章

Copyright @ 2022~2023