二叉查找树全面剖析：原理构建及算法实践——《Hello C++ Wrold!》第十八篇（C/C++）

2个月前发布 gsjqwyl
13 0 0

深度解析二叉搜索树：原理构造与算法实践——《Hello C++ World!》第十八章（C/C++）

文章目录

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

前言

二叉搜索树（Binary Search Tree，简称BST）作为一种关键的数据结构，在计算机科学领域应用广泛。它凭借基于键值的有序特性，能高效支持数据的插入、删除和查找等操作，是诸多复杂算法与系统的基础构件。本文将围绕二叉搜索树展开全面且深入的探究。首先，从其核心定义与重要性质入手，协助读者建立对二叉搜索树的基本认知，涵盖其中序遍历可获取升序序列这一重要特性。随后，细致剖析二叉搜索树的各类基本操作，诸如插入、查找、删除等，并通过C++代码实现进行具体示例，同时对比递归与非递归实现方式的差异。此外，还将对二叉搜索树与有序数组的二分查找进行对比分析，明确各自的优势与局限。最后，结合一系列经典算法题目，像二叉搜索树与双向链表的转换、依据遍历序列构建二叉树、二叉树的非递归遍历等，展现二叉搜索树在实际问题中的应用，助力读者巩固所学知识，提升解决复杂问题的能力。无论是数据结构的初学者，还是期望深化对二叉搜索树理解的开发者，均可从本文中获取有价值的参考。

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

概念

二叉搜索树是一棵空树或者具备以下特性的二叉树：
1. 若左子树非空，则左子树上所有节点的值均小于根节点的值；
2. 若右子树非空，则右子树上所有节点的值均大于根节点的值；
3. 其左右子树也各自为二叉搜索树。

引申

  • a. 通过中序遍历二叉搜索树可得到升序序列；
  • b. 查找其中元素的最坏时间复杂度为O(n)（n表示元素个数）；
  • c. 结点左侧所有子树的值均小于该结点值，结点右侧所有子树的值均大于该结点值。

例如：在这里插入图片描述

二叉搜索树的模拟实现

以下是用C++模板实现的二叉搜索树节点及类定义。模板结构体BSTreeNode定义了节点的左右子节点和键值，模板类BSTree包含了树的根节点以及插入、查找、删除、中序遍历等操作的实现。例如，插入操作通过循环找到合适位置插入新节点，查找操作通过循环遍历树来判断元素是否存在，删除操作则根据节点是否有子节点分情况处理，中序遍历通过递归实现。

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;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(key);
        if (key > parent->_key)
        {
            parent->_right = cur;
        }
        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;
                    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;
    }

private:
    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对于基本类型交换值，对于指针交换指针存储的值；
    1. 二叉搜索树删除操作的模拟实现分情况：无孩子直接删，有一个孩子托孤，有两个孩子用替换法（与左子树最右或右子树最左结点替换后删除）；
    1. 引用在底层汇编中有空间占用，但日常使用是不额外开空间。

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

二分查找在插入和删除操作上效率欠佳，而二叉搜索树在查找、排序、插入、删除等操作上效率尚可，但存在下限较低的问题，如图：在这里插入图片描述

两个搜索模型

  1. 键值搜索模型：可快速判断元素是否存在，例如门禁系统、小区车辆出入系统等场景。做法是将词库读取到二叉搜索树中，然后读取单词判断是否存在，不存在则为拼写错误。
  2. key/value搜索模型：通过一个值查找另一个值，例如商场车辆出入系统、高铁实名制车票系统等场景。举例来说统计水果出现次数，第一次出现时插入水果名和出现次数1，非第一次时直接将次数加1。需注意key一般为不重复信息，在k-v模型中，二叉搜索树的模拟实现里成员变量需添加value，插入和删除操作的形参也需添加value。

作业部分

题目

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

引申

使用两个遍历结果确定树的结构时，其中必须有一个是中序遍历结果，如此才能确定树的结构。

力扣相关题目

牛客网 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->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. 根据二叉树创建字符串

该题关键在于处理括号的情况：1.左边为空、右边不为空时，左边和右边的括号均需保留；2.左边不为空、右边为空时，仅保留左边的括号；3.左边和右边均为空时，两边的括号均不保留。需注意将root->val转换为字符串类型。

代码示例：

/**
 * 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. 二叉树的最近公共祖先

做法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. 从前序与中序遍历序列构造二叉树

做法是利用前序确定根的位置，通过中序分割左右区间。需注意root创建空间时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>& 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 = preorder.size() - 1; int p = 0;
        return _build(preorder, inorder, p, 0, n);
    }
};

自己实现的函数：在这里插入图片描述

力扣 106. 从中序与后序遍历序列构造二叉树

与前一题的区别在于previ从最后开始取，构建完根后先构建右树。

代码

© 版权声明
文章版权归作者所有，未经允许请勿转载。
上一篇

没有更多了...

下一篇

没有更多了...

相关文章

没有相关内容!

暂无评论

none
暂无评论...

Jetbrains官方授权

官方正版 JetBrains 账号

登录即可使用全家桶 不限操作系统 官方授权 支持全家桶所有软件 不限版本
🔥 最低 32元/年