目录

​编辑

二叉搜索树的定义，创建（Key模型）

定义

创建

 基本操作

插入

查找

删除

Key模型和Key_Value模型 

二叉搜索树（Key_Value模型） 

定义

创建

基本操作

 插入

 应用

---

二叉搜索树的定义，创建（Key模型）

定义

BST = BinarySearchTree。

每个节点包含一个键（key）和两个指针，分别指向其左子树和右子树。

• 左子树上的所有节点的键值都小于其父节点的键值。
• 右子树上的所有节点的键值都大于其父节点的键值。
• 每个子树也是一棵二叉搜索树。

 

创建

 定义一个模板类BSTreeNode

• 用于表示二叉搜索树中每个节点的结构，包含指向左右子节点的指针以及节点存储的关键字。

同时定义另一个模板类BSTree

• 使用BSTreeNode来构成实际的二叉搜索树结构，包含对树根节点的引用。

// 定义一个模板类，用于表示二叉搜索树的节点
template<class K>
struct BSTreeNode
{
    // 指向左子节点的指针
    BSTreeNode<K>* _left;
    // 指向右子节点的指针
    BSTreeNode<K>* _right;
    // 节点存储的关键字
    K _key;

    // 构造函数，初始化节点的关键字，并将左右子节点指针设为nullptr
    BSTreeNode(const K& key)
        :_left(nullptr)  // 初始化左子节点指针为nullptr
        , _right(nullptr) // 初始化右子节点指针为nullptr
        , _key(key)       // 初始化节点关键字
    {
    }
};

// 定义一个基于BSTreeNode<K>的二叉搜索树类模板
template<class K>
class BSTree
{
    // 为方便起见，定义一个类型别名，代表BSTreeNode<K>类型
    typedef BSTreeNode<K> Node;

private:
    // 指向二叉搜索树根节点的指针，默认初始化为nullptr
    Node* _root = nullptr;
};

 基本操作

插入

将一个新的键值插入到BST（Binary Search Tree）中，保持BST的特性。

具体过程：

• 树为空，则直接新增节点，赋值给root指针
• 树不空，按二叉搜索树性质查找插入位置，插入新节点 

// 插入函数，将给定的关键字插入到二叉搜索树中
bool Insert(const K& key)
{
    // 判断树是否为空，若为空则直接在根节点插入新节点并返回true
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }

    // 初始化父节点指针和当前遍历节点指针   
    Node* parent = nullptr;    //存储上一次节点
    Node* cur = _root;

    // 循环查找插入位置，直到找到空位置或遇到相同关键字的节点
    while (cur)  
    {
        // 节点关键字小于待插入关键字，向右子树移动
        if (cur->_key < key)    
        {
            parent = cur;
            cur = cur->_right;
        }
        // 节点关键字大于待插入关键字，向左子树移动
        else if (cur->_key > key)   
        {
            parent = cur;
            cur = cur->_left;
        }
        // 遇到相同关键字，二叉搜索树不允许数据冗余，返回false
        else
        {
            return false;
        }
    }

    // 创建新节点，初始化关键字
    Node* node = new Node(key);

    // 将新节点插入到父节点的适当子树（根据大小决定是左子树还是右子树）
    if (parent->_key < key)
    {
        parent->_right = node;
    }
    else
    {
        parent->_left = node;
    }

    // 插入成功，返回true
    return true;
}

首先检查树是否为空，然后通过循环比较找到插入位置。

如果遇到相同关键字的节点，则因为二叉搜索树的性质不可冗余（每个节点的关键字都大于其左子树中所有节点的关键字且小于其右子树中所有节点的关键字），插入失败并返回false。

否则，找到合适的空位后创建新节点并插入到树中，最后返回true表示插入成功。

查找

查找BST中是否存在一个特定的键值；

基于二叉搜索树的结构的特点：左节点小于根，右节点大于根；

• 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
• 最多查找高度次，走到到空，还没找到，这个值不存在。

// 查找函数，判断二叉搜索树中是否存在给定的关键字
bool Find(const K& key)
{
    // 如果树的根节点为空，说明树为空，直接返回false表示未找到
    if (_root == nullptr)
    {
        return false;
    }

    // 初始化当前遍历的节点为根节点
    Node* cur = _root;

    // 在树中循环查找关键字
    while (cur)
    {
        // 如果当前节点的关键字小于待查找关键字，转向右子节点继续查找
        if (cur->_key < key)
        {
            cur = cur->_right;
        }
        // 如果当前节点的关键字大于待查找关键字，转向左子节点继续查找
        else if (cur->_key > key)
        {
            cur = cur->_left;
        }
        //找到了匹配的键 ,返回true
        else
        {
            return true;
        }
    }

    // 循环结束未找到匹配的键，返回false
    return false;
}

在二叉搜索树中查找给定的关键字是否存在。

• 从树的根节点开始，根据比较结果沿着左子树或右子树进行递归查找。
• 如果找到关键字相同的节点，则返回true；
• 如果遍历完所有可能的路径仍未找到，则返回false；表示该关键字不在树中。

删除

从BST中删除一个键值，并重新组织树以保持BST的特性。

如果找到了要删除的节点，接下来需要根据该节点的子节点数量来决定删除策略：

叶子节点：

• 直接删除该节点。

一个子节点：

• 判断该子节点在待删除的节点左右子树，根据其来用待删除节点的父节点链接其子节点；

两个子节点：

• 在待删除节点的左右子树找其替换节点（在左子树寻找最大节点或者在右子树寻找最小节点），替换后，让其链接到原待删除节点的父节点合适的位置上。

注：叶子节点和一个子节点可以整合到一起处理；

 

// 删除函数，从二叉搜索树中删除给定值的节点
bool Erase(const K& val)
{
    // 初始化当前节点指针和父节点指针
    Node* cur = _root;
    Node* parent = nullptr;

    // 查找要删除的节点
    while (cur)
    {
        // 根据键值比较结果在树中向下搜索
        if (cur->_key < val)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > val)
        {
            parent = cur;
            cur = cur->_left;
        }
        // 找到要删除的节点
        else
        {
            // 处理三种情况：叶子节点、只有左子节点、只有右子节点、左右子节点均存在
                        //叶子节点和只有一个子节点 可一起处理

            // 情况1：当前节点没有左子节点
            if (cur->_left == nullptr)
            {
               
                if (cur == _root)      // 如果是根节点    删除根节点需要更新根节点的指向
                {
                    _root = cur->_right;
                }
                // 更新父节点的子指针以绕过被删除节点
                else if (parent->_left == cur)
                {
                    parent->_left = cur->_right;
                }
                else
                {
                    parent->_right = cur->_right;
                }
                delete cur;
            }
            // 情况2：当前节点没有右子节点
            else if (cur->_right == nullptr)
            {
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else if (parent->_left == cur)
                {
                    parent->_left = cur->_left;
                }
                else
                {
                    parent->_right = cur->_left;
                }
                delete cur;
            }
            // 情况3：当前节点左右子节点均不为空
            else
            {
                // 找到右子树中的最小节点及其父节点
                Node* rightMinParent = cur;
                Node* rightMin = cur->_right;

                while (rightMin->_left)
                {
                    rightMinParent = rightMin;
                    rightMin = rightMin->_left;
                }

                // 将要删除节点的值替换为右子树中的最小值，然后删除那个最小值节点
                std::swap(cur->_key, rightMin->_key);

                // 更新最小值节点的父节点的子指针，绕过被删除的最小值节点
                if (rightMinParent->_left == rightMin)
                {
                    rightMinParent->_left = rightMin->_right;
                }
                else
                {
                    rightMinParent->_right = rightMin->_right;
                }
                //释放待删除节点资源
                delete rightMin;
            }
            // 删除操作完成，返回true
            return true;
        }
    }
    // 未找到要删除的值，返回false
    return false;
}

首先通过循环查找要删除的节点；

然后根据节点的子节点情况执行不同的删除逻辑：

• 叶子节点和只有一个子节点时，用该子节点替换删除节点的位置；
• 有两个子节点时，找到右子树的最小节点，用其值替换待删除节点的值，然后删除右子树中的这个最小节点。

最后，根据删除操作的结果返回true或false。

Key模型和Key_Value模型 

两种不同的数据存储和检索方式

Key模型

•  Key模型通常指的是数据结构中只关注唯一标识符（Key）的一种简单模式，在这种模型下，通过唯一的Key来识别和访问，不直接关联任何值或者额外信息。

例如：

        给出一个单词，判断是否拼写正确，只需要将所有单词存储后，进行搜索判断，存在就正确，不存在就错误。

Key_Value模型 

• 一种数据存储模型，其中每个条目由两部分组成：一个Key（键）和一个与之对应的Value（值） 

例如：

        同样给出一个单词，但是输出的是其中文意思，一种对应关系。

二叉搜索树（Key_Value模型） 

定义

每个节点包含三个部分：一个键（Key），一个值（Value），以及两个指向其子节点的指针（分别指向左子树和右子树）。

创建

每个节点不仅包含一个key用于维持树的排序特性，还包含一个与key相对应的value

// 定义一个模板类，表示二叉搜索树的节点，支持键值对（Key-Value）模型
template<class K, class V>
struct BSTreeNode
{
    // 指向左子节点的指针
    BSTreeNode<K, V>* _left;

    // 指向右子节点的指针
    BSTreeNode<K, V>* _right;

    // 节点存储的键（Key）
    K _key;
    // 节点存储的值（Value）
    V _value;

    // 构造函数，接收键和值作为参数，初始化节点的键和值，并将左右子节点指针设为nullptr
    BSTreeNode(const K& key, const V& value)
        :_left(nullptr)  // 初始化左子节点指针为nullptr
        , _right(nullptr)        // 初始化右子节点指针为nullptr
        , _key(key)         // 初始化节点的键
        , _value(value)     // 初始化节点的值
    {}
};

// 定义一个基于BSTreeNode<K, V>的二叉搜索树类模板
template<class K, class V>
class BSTree
{
    // 重命名，简化BSTreeNode<K, V>
    typedef BSTreeNode<K, V> Node;

public:    
    //操作，比如 删除，插入等
private:   
    // 树的根节点指针，默认初始化为nullptr
    Node* _root = nullptr;
};

基本操作

 插入

其实只有一些细微的差别，

// 插入函数，向二叉搜索树中添加一个新的键值对
bool Insert(const K& key, const V& value)
{
    // 如果树为空（根节点为nullptr），则创建一个新的节点作为根节点
    if (_root == nullptr)
    {
        _root = new Node(key, value);
        return true; // 插入成功
    }

    // 初始化父节点指针和当前遍历的节点指针
    Node* parent = nullptr;
    Node* cur = _root;

    // 寻找插入位置，循环直到找到叶子节点
    while (cur)
    {
        // 如果当前节点的键小于待插入的键，说明新节点应在其右子树中，更新父节点和当前节点
        if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }
        //与上同理
        else if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }
        // 如果键已经存在于树中，则不允许插入重复键，返回false
        else
        {
            return false;
        }
    }

    // 创建新节点，使用传入的键和值进行初始化
    cur = new Node(key, value);

    // 将新节点插入到找到的正确位置，根据父节点的键与新节点键的比较结果决定是左子节点还是右子节点
    if (parent->_key < key)
    {
        parent->_right = cur; // 插入为右子节点
    }
    else
    {
        parent->_left = cur; // 插入为左子节点
    }

    return true; // 插入操作成功完成
}

 应用

根据输入的单词，输出对应中文意思；

void TestBSTree()
	{
		BSTree<string, string> dict;
		dict.Insert("string", "字符串");
		dict.Insert("left", "左边");
		dict.Insert("insert", "插入");
		//...

		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "无此单词，请重新输入" << endl;
			}
		}
	}