图源：文心一言

考研笔记整理8k+字，小白友好、代码可跑，请小伙伴放心食用~~🥝🥝

第1版：查资料、写BUG、画导图、画配图~🧩🧩

参考用书：王道考研《2024年数据结构考研复习指导》

参考用书配套视频：7.3_1 二叉排序树_哔哩哔哩_bilibili

特别感谢： Chat GPT老师、文心一言老师~

📇目录

🦮思维导图

🧵基本概念

⏲️定义

🌰推算举栗

⌨️代码实现

🧵分段代码

🔯P0：调用库文件

🔯P1：定义结点与指针

🔯P2：封装创建结点

🔯P3：插入结点

🔯P4：构造二叉树

🔯P5：树的遍历

🔯P6：结点查询

🔯P7：结点删除

🔯P8：main函数

🧵完整代码

🔯P0：完整代码

🔯P1：执行结果

🔚结语

🦮思维导图

备注：

思维导图为整理王道教材第7章查找的所有内容；
本篇仅涉及到朴素二叉排序树（BST）的代码；
后期会在博文列表中整理平衡树、红黑树的相关内容[交可爱Ada小助手布置的红黑树作业]，也可能会增加B树、线性查找的相关内容~ //博文写作时间很长，但是愿意点赞的小伙伴很少，因此还在犹豫中~😶‍🌫️😶‍🌫️

🧵基本概念

⏲️定义

二叉排序树，若树非空，满足下列特性：
若左子树非空：左子树上所有结点的值＜根结点的值；
若右子树非空：右子树上所有结点的值＞根结点的值；
左、右子树分别是一棵二叉排序树。
简而言之，满足“ 左子树结点值 < 根结点值＜右子树结点值 ” 的二叉树。

树的插入操作：与结点进行比较，小于则向左子树遍历，大于则向右子树遍历，直到遍历为空结点时，插入该结点。因此，插入的结点均为叶子结点。

注意：同一个序列不同的输入顺序，可能会得到不同的二叉树~

🌰推算举栗

输入序列为递增/递减序列，或者从两端向中间逼近，例如：{3、7、8、9、10、15}、{15、3、7、10、9、8}，这种就很容易形成度为1的长树~
输入序列为从中间向两段逼近，例如：{8、7、10、3、9、15}，这种就很容易形成比较理想的宽树形[度为2]，甚至是平衡树~ //这棵树的创建过程博文后会详细说明~

平衡树的定义，可见：🌸数据结构05：树与二叉树[C++]

ASL：平均查找长度，计算方式为 Σ（第 i 层结点数 x i 的层高）/ （结点个数），表示整棵树所有查找过程中，进行关键字比较次数的平均值~
通过图中比较，可知：
左侧树的查找：接近链表，与顺序查找相似，时间复杂度近似O(n)；
右侧树的查找：接近平衡树，与折半查找相似，时间复杂度近似O(log n)；
因此，朴素二叉排序树的查找的时间复杂度在O(n)~O(log n)波动，可以通过尽量调整树的高度以降低时间复杂度[🌸涉及到平衡二叉树，算法会在下一篇博文中提到]~

下面我们以图中右侧的小树为例，说明如何创建及遍历朴素二叉排序树~

图源：文心一言

⌨️代码实现

🧵分段代码

🔯P0：调用库文件

此次用到输入输出流文件iostream与创造动态数组的向量vector~

#include <iostream>
#include <vector>

🔯P1：定义结点与指针

typedef struct BSTNode {int data;    //数据域struct BSTNode *lchild, *rchild;    //左孩子指针、右孩子指针
}BSTNode,*BiTree;    //结点BSTNode，指针BiTree

🔯P2：封装创建结点

创建结点的步骤在创建树时重复出现，因此使用函数封装~

思路：(1)创建结点、(2)赋值、(3)指针置空，(4)返回结点~

//创建结点
BSTNode* CreateNode(int data) {BSTNode* newNode = new BSTNode();    //新建结点newNode->data = data;         //赋值数据域newNode->lchild = nullptr;    //指针置空newNode->rchild = nullptr;return newNode;               //返回结点
}

🔯P3：插入结点

采用递归的方式创建树，朴素二叉树插入的结点通常为叶节点：

若二叉排序树为空，则创建根结点；若结点为空，则插入结点。
若二叉树不为空：
关键字 = 根结点值，树中已有此元素；
关键字＜根结点值，继续遍历左子树；
关键字＞根结点值，继续遍历右子树。

int BST_Insert(BiTree &tree, int key) {if (tree == NULL) {            //若树为空，创建根结点；若遍历到结点为空，插入结点tree = CreateNode(key);return 1;}else if(key == tree->data)     //若结点已在树中存在，返回错误return 0;else if(key < tree->data)      //若待插入结点＜关键字return BST_Insert(tree->lchild,key);    //向左子树查找else                           //若待插入结点＞关键字return BST_Insert(tree->rchild,key);    //向右子树查找
}

🔯P4：构造二叉树

通过main函数中声明的树地址BiTree &tree，以及传入的整数型动态数组std::vector<int> &vec，通过调用P3插入结点的函数完成树的创建~

void Creat_BST(BiTree &tree, std::vector<int> &vec){tree = nullptr;    //初始时树置空//将main中传入的数组，每个元素以插入的操作完成树的创建for(int i = 0; i < vec.size(); i++){    BST_Insert(tree, vec[i]);}
}

具体的创建过程可参考下图~

🔯P5：树的遍历

传入树的根结点内存地址，由于二叉树遵循：“左＜根＜右” 的原则，因此可以通过二叉树的中序遍历完成，此处采用递归方式完成~

void InOrderTraversal(BiTree tree) {if (tree == nullptr)    //如果树为空，返回return;InOrderTraversal(tree->lchild);    //遍历左子树std::cout << tree->data << " ";    //输出当前结点的值InOrderTraversal(tree->rchild);    //遍历右子树
}

如果我没记错的话，运行起来应该是这样的~

树指针的路径一路向左，结点8、结点7、结点3[以上3个结点入系统调用栈]，结点3没有左孩子，打印结点3，结点3出栈；
结点3没有右孩子结点，系统调用栈退1位，结点7出栈，打印结点7；
结点7没有右孩子结点，系统调用栈退1位，结点8出栈，打印结点8；
结点8没有右孩子结点，栈为空，向结点8的右子树结点10的左子树结点9移动[结点10、结点9入系统调用栈]，结点9没有左孩子，打印结点9，出栈；
结点9没有右孩子结点，系统调用栈退1位，结点10出栈，打印结点10；
结点10具有右孩子结点，打印结点10的右孩子结点15；
结点15没有孩子结点，且系统调用栈空，结束递归过程。

对于中序遍历原理感兴趣的小伙伴可以参考： 🌸数据结构05：树与二叉树[C++]，该篇博文也含非递归方式先序、中序、后序遍历树的代码 [ 区别就是手动创建了一个调用栈 ]~

🔯P6：结点查询

此处为了方便后序的删除操作，函数这边写成了结点的形式BSTNode*，需要传入两个值，树的地址BiTree tree和关键字int key~

若树非空，且查询的值key与树中当前结点的值不同：
查询的值key < 树中当前结点的值，向左子树走；
查询的值key > 树中当前结点的值，向右子树走；
若树为空或未找到结点，输出：未找到结点；
除上述情况，输出：找到目标结点，与查询的值key 。

BSTNode* LocateElem(BiTree tree, int key) {while (tree != nullptr && key != tree->data) {    //树非空，且结点与关键字不等if (key < tree->data)    //关键字 < 结点，向左子树查询tree = tree->lchild;else                     //关键字 > 结点，向左子树查询tree = tree->rchild;}if (tree == nullptr) {    //数为空遍历结束，未找到结点，返回std::cout << "未找到目标节点\n";return nullptr;} else {                  //反馈信息：找到目标结点std::cout << "找到目标节点：" << tree->data << "\n";return tree;}
}

🔯P7：结点删除

删除的情况略微复杂，传入树的地址BiTree tree和关键字int key~

删除可分为以下4种情况考虑——

叶子结点：
删除结点对于树的结构没有影响~
当前孩子的父节点→NULL，并删除本结点~
单左子树结点：
删除结点时，其相邻的右孩子结点需要替代本结点的位置~
当前孩子的父节点→当前孩子的子结点，并删除本结点~
单右子树结点：
删除结点时，其相邻的左孩子结点需要替代本结点的位置~
当前孩子的父节点→当前孩子的子结点，并删除本结点~
双子树结点：
删除结点时，其右子树最大的结点（即中序遍历后继结点）需要替代本结点的位置~
当前结点的数值==中序遍历后继结点的数值~
但中序遍历后继结点此时可能会有孩子结点，因此需要其当前孩子的父节点→当前孩子的子结点（同单子树结点）~

有点绕对不对，用图模拟一下这个过程，如果我没有理解错的话是这样的~

void BST_Delete(BiTree& tree, int key) {if (tree == nullptr) {return;  // 树为空，直接返回}BiTree parent = nullptr;  // 记录要删除结点的父节点BiTree current = tree;    // 当前遍历到的结点// 查找要删除的结点以及其父节点while (current != nullptr && current->data != key) {parent = current;if (key < current->data) {current = current->lchild;  // 向左子树查找} else {current = current->rchild;  // 向右子树查找}}if (current == nullptr) {return;  // 未找到要删除的结点}// 根据不同情况进行删除if (current->lchild == nullptr && current->rchild == nullptr) {// 叶子结点，直接删除if (parent == nullptr) {tree = nullptr;  // 删除的是根结点} else if (parent->lchild == current) {parent->lchild = nullptr;  // 删除的是左子结点} else {parent->rchild = nullptr;  // 删除的是右子结点}delete current;  // 释放内存} else if (current->lchild == nullptr) {// 左子树为空，用右子树替代当前结点if (parent == nullptr) {tree = current->rchild;  // 删除的是根结点} else if (parent->lchild == current) {parent->lchild = current->rchild;  // 删除的是左子结点} else {parent->rchild = current->rchild;  // 删除的是右子结点}delete current;  // 释放内存} else if (current->rchild == nullptr) {// 右子树为空，用左子树替代当前结点if (parent == nullptr) {tree = current->lchild;  // 删除的是根结点} else if (parent->lchild == current) {parent->lchild = current->lchild;  // 删除的是左子结点} else {parent->rchild = current->lchild;  // 删除的是右子结点}delete current;  // 释放内存} else {// 左右子树都不为空，用右子树中最小的结点替代当前结点BiTree minNode = current->rchild;  // 最小结点BiTree minNodeParent = current;    // 最小结点的父节点while (minNode->lchild != nullptr) {minNodeParent = minNode;minNode = minNode->lchild;}current->data = minNode->data;  // 用最小结点的值替代当前结点的值if (minNodeParent == current) {minNodeParent->rchild = minNode->rchild;  // 最小结点是当前结点的右子结点} else {minNodeParent->lchild = minNode->rchild;  // 最小结点是当前结点右子树的最左子结点}delete minNode;  // 释放内存}
}

🔯P8：main函数

main函数除了P0~P6的函数调用，就创建了1棵树，以及示意性地增加了与删除了结点~

int main() {BiTree tree = nullptr;//BiTree root = nullptr;// 增加结点：动态数组std::vector<int> vec = {8, 7, 10, 3, 9, 15};Creat_BST(tree, vec);//root = tree;  // 记录根节点的指针std::cout << "\n";// 输出结点：中序遍历std::cout << "遍历二叉树: ";InOrderTraversal(tree);std::cout << "\n";// 按值查找[本例为7]int target = 7;LocateElem(tree, target);//插入结点int node2 = 11;BST_Insert(tree, node2);std::cout << "插入节点：" << node2 << "\n";//删除结点int node3 = 8;BST_Delete(tree, node3);std::cout << "删除节点：" << node3 << "\n";// 输出结点：中序遍历std::cout << "遍历二叉树: ";InOrderTraversal(tree);std::cout << std::endl;return 0;
}

🧵完整代码

🔯P0：完整代码

为了凑本文的字数，我这里贴一下整体的代码，删掉了细部注释~

Ps：改掉了以往博文二叉树需要手动输入结点搭建的缺点，扔到C++在线网站就可以测~🫥🫥

//头文件
#include <iostream>
#include <vector>//结点结构
typedef struct BSTNode{int data;struct BSTNode *lchild, *rchild;
}BSTNode,*BiTree;//创建结点
BSTNode* CreateNode(int data) {BSTNode* newNode = new BSTNode();newNode->data = data;newNode->lchild = nullptr;newNode->rchild = nullptr;return newNode;
}//插入结点
int BST_Insert(BiTree &tree, int key) {if (tree == NULL) {tree = CreateNode(key);return 1;}else if(key == tree->data)return 0;else if(key < tree->data)return BST_Insert(tree->lchild,key);elsereturn BST_Insert(tree->rchild,key);
}//创建树
void Creat_BST(BiTree &tree, std::vector<int> &vec){tree = nullptr;for(int i = 0; i < vec.size(); i++){BST_Insert(tree, vec[i]);}
}//中序遍历
void InOrderTraversal(BiTree tree) {if (tree == nullptr)return;InOrderTraversal(tree->lchild);std::cout << tree->data << " ";InOrderTraversal(tree->rchild);
}//按值查找
BSTNode* LocateElem(BiTree tree, int key) {while (tree != nullptr && key != tree->data) {if (key < tree->data)tree = tree->lchild;elsetree = tree->rchild;}if (tree == nullptr) {std::cout << "未找到目标节点\n";return nullptr;} else {std::cout << "找到目标节点：" << tree->data << "\n";return tree;}
}//删除结点
void BST_Delete(BiTree& tree, int key) {if (tree == nullptr) {return;}BiTree parent = nullptr;BiTree current = tree;  // 查找要删除的结点以及其父节点while (current != nullptr && current->data != key) {parent = current;if (key < current->data) {current = current->lchild;  } else {current = current->rchild; }}if (current == nullptr) {return; }// 根据不同情况进行删除if (current->lchild == nullptr && current->rchild == nullptr) {// 叶子结点，直接删除if (parent == nullptr) {tree = nullptr; } else if (parent->lchild == current) {parent->lchild = nullptr; } else {parent->rchild = nullptr; }delete current;} else if (current->lchild == nullptr) {// 左子树为空，用右子树替代当前结点if (parent == nullptr) {tree = current->rchild; } else if (parent->lchild == current) {parent->lchild = current->rchild; } else {parent->rchild = current->rchild; }delete current;} else if (current->rchild == nullptr) {// 右子树为空，用左子树替代当前结点if (parent == nullptr) {tree = current->lchild; } else if (parent->lchild == current) {parent->lchild = current->lchild; } else {parent->rchild = current->lchild; }delete current; } else {// 左右子树都不为空，用右子树中最小的结点替代当前结点BiTree minNode = current->rchild; BiTree minNodeParent = current;  while (minNode->lchild != nullptr) {minNodeParent = minNode;minNode = minNode->lchild;}current->data = minNode->data; if (minNodeParent == current) {minNodeParent->rchild = minNode->rchild; } else {minNodeParent->lchild = minNode->rchild; }delete minNode; }
}int main() {BiTree tree = nullptr;std::vector<int> vec = {8, 7, 10, 3, 9, 15};Creat_BST(tree, vec);std::cout << "\n";std::cout << "遍历二叉树: ";InOrderTraversal(tree);std::cout << "\n";int target = 7;LocateElem(tree, target);int node2 = 11;BST_Insert(tree, node2);std::cout << "插入节点：" << node2 << "\n";int node3 = 8;BST_Delete(tree, node3);std::cout << "删除节点：" << node3 << "\n";std::cout << "遍历二叉树: ";InOrderTraversal(tree);std::cout << std::endl;return 0;
}