二叉搜索树深度解析：从原理实现到算法应用----《Hello C++ Wrold!》(18)--(C/C++)

文章目录

• 前言
• 二叉搜索树（二叉排序树或二叉查找树）
• • 二叉搜索树的模拟实现
  • 二叉搜索树和有序数组二分查找的比较
  • 两个搜索模型
• 作业部分

前言

二叉搜索树（Binary Search Tree，简称 BST）作为一种重要的树形数据结构，在计算机科学领域有着广泛的应用。它凭借其基于键值的有序性，能够高效地支持数据的插入、删除和查找等操作，是许多复杂算法和系统的基础组件。

本文将围绕二叉搜索树展开全面而深入的探讨。首先，我们将从其核心定义和关键性质出发，帮助读者建立对二叉搜索树的基本认知，包括其通过中序遍历可得到升序序列这一重要特性。随后，详细剖析二叉搜索树的各项基本操作，如插入、查找、删除等，并通过 C++ 代码实现进行具体演示，同时对比递归与非递归实现方式的异同。

此外，我们还将对二叉搜索树与有序数组的二分查找进行对比分析，明确各自的优势与局限。最后，结合一系列经典的算法题目，如二叉搜索树与双向链表的转换、根据遍历序列构造二叉树、二叉树的非递归遍历等，展示二叉搜索树在实际问题中的应用，帮助读者巩固所学知识，提升解决复杂问题的能力。无论是数据结构初学者，还是希望深化对二叉搜索树理解的开发者，都能从本文中获得有价值的参考。

二叉搜索树（二叉排序树或二叉查找树）

概念:是一颗空树或者是具有以下性质的二叉树:

1.若左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

引申:a.用中序遍历去遍历二叉搜索树的结果正好是升序

 b.查找其中元素的最坏时间复杂度是O(n)--n表示n个元素

比如:

c.结点左边所有的树都比结点小;结点右边所有的树都比结点大

二叉搜索树的模拟实现

template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public:BSTree():_root(nullptr){} BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);//理解!return *this;}~BSTree(){Destroy(_root);}bool Insert(const K& key)//插入不了重复的值{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (key>cur->_key){parent = cur;cur = cur->_right;}else if(key< cur->_key){parent = cur;cur = cur->_left;//cur只是里面存的值变成了他的}else{return false;}}cur = new Node(key);//把开辟好的地址存在了cur里面if (key > parent->_key){parent->_right = cur;//本来里面是nullptr;}else{parent->_left = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return true;}}return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else // 找到了{ // 左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}// 右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}  // 左右都不为空 else{// 找替代节点Node* parent = cur;//这里不能是nullptr,不然要删的地方是根节点就惨了Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;//这个就是左子树存在右子树的情况}//这里要注意!!!cur = leftMax;}delete cur;return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}/*bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}*/用递归实现这些函数private:/*bool _EraseR(Node*& root, const K& key)这种树形递归的话一般都要传这个root{if (root == nullptr)return false;if (root->_key _right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 1、左为空// 2、右为空// 3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;这里可不是传的引用while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);这里不能是(leftMax,key)!!! 倒不是它是局部变量的关系}delete del;return true;}}bool _InsertR(Node*& root, const K& key)这里用&就非常好{if (root == nullptr){root = new Node(key);return true;}if (root->_key _right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key _right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}*/这是用递归实现的函数void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << \" \";_InOrder(root->_right);} Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copyroot = new Node(root->_key);copyroot->_left = Copy(root->_left);copyroot->_right = Copy(root->_right);return copyroot;}//这里用的是前序遍历,用中序可不行void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}private:Node* _root;};

引申:1.swap对于基本类型，交换的是值;对于指针，交换的是指针里面存的值

 2.二叉搜索树的删除操作的模拟实现做法:

找到后分情况:1.结点没有孩子--直接删2.结点有一个孩子--托孤3.结点有两个孩子--替换法:该结点跟左子树的最右(最大)结点或右子树的最左(最小)结点替换,然后删除

3.关于引用,平时说的话就是不开空间,探讨底层汇编才考虑它其实是占了空间的

二叉搜索树和有序数组二分查找的比较

二分查找的话，插入和删除的效率不太行

二叉搜索树的话，查找排序插入删除效率都不错，但是下限太低了,如图:

两个搜索模型

1.key的搜索模型:快速判断在不在

eg:门禁系统 小区车辆出入系统

比如:检查一篇英文文章，看单词是否拼写正确做法:读取词库到一颗搜索树上，读取单词，看在不在-不在就是拼写错误

2.key/value的搜索模型:通过一个值找另外一个值

eg:商场的车辆出入系统 高铁实名制车票系统

举例:统计水果出现的次数做法:第一次出现的话，要插入这个水果名和它出现的次数为1 不是第一次的话，直接次数++就行了

注意:key一般是不允许重复的信息!

k-v模型的话，在上面的二叉搜索树的模拟实现里面,成员变量要加个value,Insert和erase操作的形参要加value

作业部分

下面关于二叉搜索树正确的说法是（C）A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点B.给定一棵二叉搜索树的前序和中序遍率历结果，无法确定这棵二叉搜索树C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树引申:使用两个遍历结果确定树的结构， 其中有一个遍历结果必须要是中序遍历结果,这样就可以

牛客网 JZ36 二叉搜索树与双向链表

牛客网 JZ36 二叉搜索树与双向链表做法:也就是把当前在的地方的left改成指向中序遍历上一个结点，把right改成指向中序遍历下一个结点 在前序遍历改结点的时候:prev一定要传引用注意:最后返回的结点多半不是开头给的那个结点 易忘这一步:if(prev) prev->right = cur;

代码展示:/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/void Inorder(TreeNode*cur,TreeNode*&prev)//这个要注意{if(cur == nullptr) return;Inorder(cur->left,prev);//第二个传cur会出事cur->left = prev;if(prev) prev->right = cur;//这个不能省，叶子结点需要这个prev = cur;Inorder(cur->right, prev);}class Solution {public: TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr;Inorder(pRootOfTree, prev);while(pRootOfTree&&pRootOfTree->left) pRootOfTree = pRootOfTree->left;return pRootOfTree; }};

引申:while和if自己老是容易写混

力扣 606. 根据二叉树创建字符串

力扣 606. 根据二叉树创建字符串这道题最主要是()的处理:1.左边为空，右边不为空->左边右边括号都保留2.左边不为空，右边为空->左边括号保留3.左边右边都为空->左边右边的括号都不保留注意:root->val记得转化成string类型的

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: string tree2str(TreeNode* root) { string s1; if(root == nullptr) return \"\"; else s1+=to_string(root->val); if(root->left||root->right) { s1+=\"(\";s1+= tree2str(root->left); s1+=\")\"; } if(root->right)// {  s1+=\"(\";s1+=tree2str(root->right); s1+=\")\"; } return s1; }};

注意理解这里局部变量s1的用法

力扣 236. 二叉树的最近公共祖先

力扣 236. 二叉树的最近公共祖先做法1:时间复杂度为O(N平方)先查找,看p,q看该结点的左边还是右边->一个在左一个在右这个结点就是最近公共祖先 在同一边就要递归去那一边再来注意:p,q其中一个可能就是最近公共祖先做法2:时间复杂度为O(n)搞了两个栈,把到p,q的路径存在了栈里面，之后根据他们的公共祖先高度应该一样来找

代码展示:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool Find(TreeNode*root,TreeNode*target,stack<TreeNode*>&path)// { if(root == nullptr) return false; path.push(root); if(root == target) return true; if(Find(root->left,target,path)) return true; if(Find(root->right,target,path)) return true; path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> p1,q1; Find(root,p,p1);Find(root,q,q1); while(p1.size()>q1.size()) p1.pop(); while(p1.size()<q1.size()) q1.pop(); while(p1.top()!=q1.top()) { p1.pop(); q1.pop(); } return p1.top(); }};

上面是做法2的Find的写法

力扣 105. 从前序与中序遍历序列构造二叉树

力扣 105. 从前序与中序遍历序列构造二叉树做法: 用前序去确定根的位置，用中序去分割左右区间（也就是中序去判断完没完）注意:root创建空间的写法: TreeNode*root = new TreeNode(preorder[previ]); previ要带引用,传参时不能传个0过去这样!

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* _build(vector<int>& preorder, vector<int>& inorder ,int&previ,int begini,int endi) { if(begini>endi) return nullptr; TreeNode*root = new TreeNode(preorder[previ]); int rooti = begini; while(rooti<=endi) { if(preorder[previ] == inorder[rooti]) break; rooti++; } ++previ; root->left = _build(preorder,inorder,previ,begini,rooti-1); root->right = _build(preorder,inorder,previ,rooti+1,endi); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = (int)preorder.size()-1; int p = 0; return _build(preorder,inorder,p,0,n); }};

自己实现的函数:

力扣 106. 从中序与后序遍历序列构造二叉树
力扣 144. 二叉树的前序遍历(自己要求自己用非递归的形式完成)
力扣 94. 二叉树的中序遍历(自己要求自己用非递归的形式完成)
力扣 145. 二叉树的后序遍历(自己要求自己用非递归的形式完成)

力扣 106. 从中序与后序遍历序列构造二叉树跟上面做法的区别:previ要从最后开始取,然后根构建完之后先构建右树代码展示:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:TreeNode* _build(vector<int>& postorder, vector<int>& inorder  ,int&previ,int begini,int endi) { if(begini>endi) return nullptr;// TreeNode*root = new TreeNode(postorder[previ]); int rooti = begini; while(rooti<=endi) { if(postorder[previ] == inorder[rooti]) break; rooti++; } --previ; root->right = _build(postorder,inorder,previ,rooti+1,endi); root->left = _build(postorder,inorder,previ,begini,rooti-1); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int p = postorder.size()-1; return _build(postorder,inorder,p,0,postorder.size()-1); }};

力扣 144. 二叉树的前序遍历(自己要求自己用非递归的形式完成)做法:访问左路结点(此时就把结点的值搞到vector里面),左路结点全入栈，后续依次访问左路结点的右子树力扣 94. 二叉树的中序遍历(自己要求自己用非递归的形式完成)做法:改成在出栈的时候再把结点存vector里就行了

代码展示:中序遍历:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<int> inorderTraversal(TreeNode* root) { vector<int>v; stack<TreeNode*> st; TreeNode* cur = root; while(cur||!st.empty()) {  while(cur)  { st.push(cur); cur = cur->left;  }  TreeNode*top = st.top();st.pop(); v.push_back(top->val);  cur = top->right; } return v; }};前序遍历:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<int> preorderTraversal(TreeNode* root) { vector<int>v; stack<TreeNode*> st; TreeNode* cur = root; while(cur||!st.empty()) {  while(cur)  { v.push_back(cur->val); st.push(cur); cur = cur->left;  }  TreeNode*top = st.top();st.pop();  cur = top->right; } return v; }};

力扣 145. 二叉树的后序遍历(自己要求自己用非递归的形式完成)做法:加一个prev来记录上一个存了的结点是啥 改成在一个结点的右子树为空或者上一个访问结点是右子树的根时再访问这个结点下面是与前面两道题相差比较大的地方

代码展示:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<int> postorderTraversal(TreeNode* root) { vector<int>v; stack<TreeNode*> st; TreeNode* cur = root; TreeNode*prev = nullptr; while(cur||!st.empty()) {  while(cur)  { st.push(cur); cur = cur->left;  }  TreeNode*top = st.top(); if(top->right== nullptr||top->right == prev)  {  v.push_back(top->val);  prev = top; st.pop();  }  else  cur = top->right; } return v; }};

二叉树的后序非递归遍历中，需要的额外空间包括（C）
A.一个栈
B.一个队列
C.一个栈和一个记录标记的顺序表
D.一个队列和一个记录标记的顺序表
注意:vector别忘了他是顺序表!