【C++】二叉搜索树

1. 一个指针指向左子树。

2. 一个指针指向右子树。

3. 一个变量存放数据。

4. 构造函数：传入数据，初始化列表进行初始化。
template<class K>
struct BSTreeNode
{
//左右指向和数据
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;

//构造
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};

2.2 树类初始结构

1. 私有成员变量只有一个根节点的指针。

2.3 Insert(插入)

1. 如果树为空，那么用待插入的值创建节点作为根节点。插入成功返回true。

2. 如果树不为空，用cur标记根节点的位置，插入的值和cur位置的值比较，比你大，cur就去右边，比你小，cur就去左边，继续比较，直到cur走到空，就在cur位置创建一个节点。连接的话需要一个前驱指针，每次cur移动之前赋值给前驱指针。

3. 如果值相等就不插入，返回false。

4. 创建完新节点后需要判断插入在上面节点的哪一边，用值比较，如果比上面大就插在右边，小就插在左边。
bool Insert(const K& key)
{
//判空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}

Node* cur = _root;
Node* prev = nullptr;
//找位置
while (cur)
{
prev = cur;

if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else
{
return false;
}
}

//建节点
cur = new Node(key);
if (key > prev->_key)
{
prev->_right = cur;
}
else
{
prev->_left = cur;
}
return true;
}
【递归版本】

1. 从根节点开始比较，你比我大就去我的右子树，你比我小就去我的左子树，相等就不插入，走到空就插入，参数是节点的引用。
bool InsertR()
{
return _InsertR(_root);
}

bool _InsertR(Node*& root, const K& key)
{
//结束条件
if (root == nullptr)
{
root = new Node(key);
return true;
}

//找位置
if (key > root->_key)
{
return _InsertR(root->_right, key);
}
else if(key < root->_key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}

2.5 Find(查找)

1. 值比较，从根节点开始比，比你小就继续往左边比，比你大就往右边，遇到相等就是找到了，走到空就是没有。
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;
}
【递归版本】

1. 比我小就去我的左子树找，比我大就去我的右子树找，相等就返回true，找到空就返回false。
bool FindR(const K& key)
{
return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key)
{
//结束条件
if (root == nullptr)
{
return false;
}

if (key > root->_key)
{
return _FindR(root->_right, key);
}
else if (key < root->_key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}

2.6 Erase(删除)

删除的节点有四种情况：

a：节点无孩子

b：节点有左孩子

c：节点有右孩子

d：节点有两个孩子

1. 先找到要删除的节点，记录前驱指针。

2. 如果删除的节点左为空，那么前驱指针指向这个节点的右，释放这个节点，同时要判断前驱指针的哪一边指向你。特殊情况：如果这个节点是根节点，那么就将它的右作为根节点。

3. 如果删除的节点右为空，和上面同理。

4. 如果删除的节点左右都空，和上面同理。

5. 如果删除的节点左右都不为空，需要替换法，一般选择左边最大或右边最小交换，先去右子树找最左边的节点，记得保留前驱指针，找到后和删除节点值交换，然后删除这个节点，前驱节点指向你的右边，记得判断前驱节点哪边指向你。
bool Erase(const K& key)
{
Node* cur = _root; 
Node* prev = nullptr;
while (cur)
{
if (key > cur->_key)
{
prev = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
prev = cur;
cur = cur->_left;
}
//开始删除
else
{
//左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (prev->_right == cur)
{
prev->_right = cur->_right;
}
else
{
prev->_left = cur->_right;
}
}
delete cur;
}
//右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (prev->_right == cur)
{
prev->_right = cur->_left;
}
else
{
prev->_left = cur->_left;
}
}
delete cur;
}
//都不为空
else
{
//找替换
Node* change = cur->_right;
Node* prev = cur;
while (change->_left)
{
prev = change;
change = change->_left;
}

swap(cur->_key, change->_key);

if (prev->_right == change)
{
prev->_right = change->_right;
}
else
{
prev->_left = change->_right;
}
delete change;
}
return true;
}
}
return false;
}
【递归版本】

1. 比我大就去右子树，比我小就去左子树，空就删除失败，相等就开始删除。

2. 删除的节点左为空，先记录当前节点，在把节点的右边赋值给自己，因为当前root是上一层的别名。

3. 删除节点右为空同理。

4. 删除节点左右都不为空，先找到右子树的最小节点，然后替换，再去交给右子树删除。
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}

if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else if(key < root->_key)
{
return _EraseR(root->_left, key);
}
else
{
if (root->_left == nullptr)
{
Node* cur = root;
root = root->_right;
delete cur;
}
else if (root->_right == nullptr)
{
Node* cur = root;
root = root->_left;
delete cur;
}
else
{
Node* change = root->_right;
while (change->_left)
{
change = change->_left;
}

swap(root->_key, change->_key);

return _EraseR(root->_right, key);
}
}
}

2.7 中序遍历

1. 左根右，遇到空就返回。

2. 先走左边，然后打印，然后走右边。

3. 由于需要传根节点，但外面拿不到，所以套一层无参的。
void InOrder()
{
_InOrder(_root);
}

void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}

_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

2.8 析构

1. 利用后序思想，先释放左再释放右，最后释放自己，然后置空，参数可以传引用。
~BSTree()
{
_Destroy(_root);
}

void _Destroy(Node*& root)
{
if (root == nullptr)
{
return;
}

_Destroy(root->_left);
_Destroy(root->_right);
delete root;
root = nullptr;
}

2.9 拷贝构造

1. 递归拷贝，先拷贝当前节点，再拷贝节点的左边，然后拷贝节点的右边。

BSTree(const BSTree<K>& bst)
{
_root = _Copy(bst._root);
}

Node* _Copy(Node* bst)
{
if (bst == nullptr)
{
return nullptr;
}

Node* newroot = new Node(bst->_key);
newroot->left = _Copy(bst->_left);
newroot->_right = _Copy(bst->_right);

return newroot;
}

2.10 赋值重载

1. 传值传参，利用拷贝构造传给参数，然后和参数交换。
BSTree<K>& operator=(BSTree<K> bst)
{
swap(_root, bst._root);
return *this;
}

3. 二叉搜索树的性能

1. 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

4. 二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。本质是判断一个值在不在。

2. KV模型：每一个关键码key，都有与之对应的值Value，既可以判断key在不在，也可以通过key查找value。

5. 编程题

5.1 二叉树的最近公共祖先

链接：. - 力扣（LeetCode）

【思路1】

1. 两个节点都在公共祖先的两边，当某个节点是祖先是特殊情况。

2. 所以分三种情况节点在两边(或者节点是祖先)，节点都在右边，节点都在左边，那么祖先从根节点开始不断往下调整。

3. 这个方法最坏情况是N方，当树是单分支的时候。

【思路2】

1. 记录两个节点的路径(记录节点)，用栈，从根节点开始入栈比较，如果找到了就不继续了，如果没找到，就去左边找，左边找到了也不找了，左边没找到就去右边找，遇到空就是没找到，每次比较都是先入栈再比较，都没找到就出栈。

2. 找到两个节点路径之后，让长的出栈，直到两个路径长度相等。

3. 路径长度相等之后，不断出栈，直到两个栈顶元素相同就停下。
class Solution 
{
public:
    bool path(TreeNode* root, TreeNode* key, stack<TreeNode*>& st)
    {
        //空节点
        if(root == nullptr)
        {
            return false;
        }

        //相等就返回
        st.push(root);
        if(st.top() == key)
        {
            return true;
        }

        //左子树找到就返回
        if(path(root->left, key, st))
        {
            return true;
        }

        //右子树找到就返回
        if(path(root->right, key, st))
        {
            return true;
        }

        //都没找到
        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        //获取路径信息
        stack<TreeNode*> pst;
        stack<TreeNode*> qst;
        path(root, p, pst);
        path(root, q, qst);

        //减去多余路径
        while(pst.size() != qst.size())
        {
            if(pst.size() > qst.size())
            {
                pst.pop();
            }
            else
            {
                qst.pop();
            }
        }

        //找出相同节点
        while(pst.top() != qst.top())
        {
            pst.pop();
            qst.pop();
        }

        return pst.top();
    }
};

5.2 二叉搜索树与双向链表

链接：二叉搜索树与双向链表_牛客题霸_牛客网

【思路】

1. 利用中序遍历，前后指针修改节点指针指向。

2. 每一层需要改变prev，需要加引用。
class Solution 
{
public:
void InOrder(TreeNode* cur, TreeNode*& prev)
{
if(cur == nullptr)
{
return;
}

InOrder(cur->left, prev);
cur->left = prev;
if(prev)
{
prev->right = cur;
}
prev = cur;
InOrder(cur->right, prev);
}
    TreeNode* Convert(TreeNode* pRootOfTree) 
{
        TreeNode* cur = pRootOfTree;
TreeNode* prev = nullptr;

InOrder(cur, prev);
TreeNode* head = pRootOfTree;
while(head && head->left)
{
head = head->left;
}
return head;
    }
};

5.3 从前序与中序遍历序列构造二叉树

链接：. - 力扣（LeetCode）

【思路】

1. 前序确定根，中序确定左右子树。前序是根左右，所以先构建左子树的根。

2. 划分左右区间，不断递归找根，同时利用返回值建立连接。

    TreeNode* Bulid(vector<int>& preorder, vector<int>& inorder, int& preIndex, int begin, int end)
    {
        if(begin > end)
        {
            return nullptr;
        }

        //找根
        int rootIndex = 0;
        while(rootIndex <= end)
        {
            if(inorder[rootIndex] == preorder[preIndex])
            {
                break;
            }
            ++rootIndex;
        }

        //左右区间递归，顺便建立连接
        TreeNode* root = new TreeNode(inorder[rootIndex]);
        ++preIndex;
        root->left = Bulid(preorder, inorder, preIndex, begin, rootIndex-1);
        root->right = Bulid(preorder, inorder, preIndex, rootIndex+1, end);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int preIndex = 0;
        TreeNode* root = Bulid(preorder, inorder, preIndex, 0, inorder.size()-1);
        return root;
    }

5.4 二叉树的前序遍历(非递归版本）

链接：. - 力扣（LeetCode）

【思路】

1. 前序是先走根，再走左，再走右。

2. 将每颗树或子树划分为左路节点和左路节点的右子树。

3. 先走左路节点，每走一个节点它就是根，然后继续走它的左边，一直到左边为空意味着根走完了左边也走完了，接着就是走右边了。

4. 通过栈实现回退的效果，下面的节点根左右都走完就回退上面的节点走它的右。
    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;
    }

原文地址：https://blog.csdn.net/m0_71164215/article/details/142672543

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：架构师：Redis RDB 和 AOF 持久化的机制详解
下一篇：AVL树&&红黑树

科创集团所属园区入驻企业北京铭镓半导体获 “硬科技”潜在独角兽企业认定
北京铭镓半导体有限公司于2020年入驻科创集团所属工宇园区，是新型高频率高功率半导体材料的产业化先行者之一，在超宽禁带半导体氧化镓材料开发及应用产业化方面实现新突破，其半绝缘型（010）铁掺衬底和该衬
阅读更多2024-10-09
OBOO鸥柏丨OLED透明触摸查询一体机数字科技触控广告屏技术前沿
吊挂透明OLED触摸屏一体机正成为博物馆数字化展示的“共同奔赴赛道选择，透过透明屏幕看到展示物品的内部结构和细节，G+G纯平面触控实现展示查询交互与互动的完美结合。相比传统的商用/工业液晶显示屏机柜，
阅读更多2024-10-09
408算法题leetcode--第22天
408算法题leetcode--第22天
阅读更多2024-10-09
oracle数据库安装和配置
安装和配置 Oracle 数据库是一个涉及多个步骤的过程。通过上述步骤，你应该能够成功安装并配置 Oracle 数据库，确保其在你的系统上正常运行。在实际使用中，务必根据需求对数据库进行进一步的配置和
阅读更多2024-10-09
Leetcode 1802. 有界数组中指定下标处的最大值
第三步，构建check函数，这里的check函数判断nums[index]为indexVal条件下，贪心构建的数组和是否小于等于maxSum。红：nums[index]的条件下，numsSum<
阅读更多2024-10-09
pandas常用数据格式IO性能对比
本文对pandas支持的一些数据格式进行IO（读写）的性能测试，大数据时代以数据为基础，经常会遇到操作大量数据的情景，数据的IO性能尤为重要，本文对常见的数据格式csv、feather、hdf5、ja
阅读更多2024-10-09
【五分钟学会】YOLO11 自定义数据集从训练到部署
YOLO11 从训练到部署，五分钟搞定！
阅读更多2024-10-09
RTSP/Onvif协议安防视频云平台EasyNVR运行后日志一直在打印error是什么原因？
解决办法：找到原始压缩包重新拷贝出easynv.ini文件到程序，随后重启即可。
阅读更多2024-10-09
PHP爬虫：获取商品SKU详细信息的利器
在电子商务领域，SKU（Stock Keeping Unit）即库存单位，是商品信息管理中的基础元素。获取商品的SKU详细信息对于电商运营者来说至关重要，它直接关系到库存管理、订单处理、客户服务等多个
阅读更多2024-10-09
Gin解说
Gin是一个用Go语言编写的高性能、开源的Web框架，它被设计为简单、快速和灵活。Gin非常适合用于构建RESTful API和微服务。
阅读更多2024-10-09

【C++】二叉搜索树

1. 二叉搜索数概念

2. 二叉搜索树模拟实现

2.1 树节点类初始结构