二叉搜索树的模拟实现

2024-08-17 08:14:58 浏览数 (1)

前言

概念

二叉搜索树，又名二叉排序树、二叉查找树，它的特点是：

① 左节点的值 < 根节点的值 ② 右节点的值 > 根节点的值 ③ 每棵子树都是二叉搜索树

由于这些特性，就使得在该树中查找值非常的方便，大于目前节点的值，就遍历右子树；小于目前节点的值，就遍历左子树。其次，二叉排序树还有以下特点：不可出现重复数据

应用

map，set，AVL树，红黑树，B树，优先队列

特点

由于左子树都小于根节点，右子树大于根节点，所以当中序遍历时，序列是升序排列的

因为这一特点，当你模拟实现时，又不知道如何检查自己实现是否正确时，就可以用用例来中序遍历输出，如果顺序不对，你就要去检查自己的代码啦ε=ε=ε=(~￣▽￣)~

模拟实现

数据结构的模拟实现无非就两个部分构成：

1、基本节点（如链表的节点ListNode） 和 数据结构(如链表List) 的构成，该部分通常由结构体或者类来定义 2、该数据结构的相关操作函数的实现

基本结构定义

拓展

在C 中，我们不用将每个节点的类型提前typedef一下，而是可以通过模板来写，这也是C 支持泛型编程的原因，它大大提高了代码的复用，在C 98的STL的实现中大量使用

结构定义

首先定义二叉树的每个节点，与普通二叉树一样，每个节点有

1、左右节点指针 2、该节点的数据值（二叉搜索树部分大多用key表示，因为除了有key结构，还有key，value结构）

代码语言：javascript复制
template<typename K>
// 类模板

// 该结构较为常用且类外要使用，因此定义为struct更方便（默认public权限）
struct BSNode/*BinarySearchTree的缩写*/
{
    BSNode<K>* left;
    BSNode<K>* right;
    K key;
    /*
        key结构：
        通常用来用于：查找某值是否存在
        现实使用场景：
        门禁系统

        key、value结构
        通常用于：
        1、确定一个值是否存在
        2、通过key查找value
        现实使用场景：
        字典
    */

    /*自定义的构造函数，当一个值被定义后，就会自动调用，这也是C  对C的改进*/
    BSNode(const K& k)
        : left(nullptr)
        , right(nullptr)
        , key(k)
    {}
};

再定义二叉树的整体数据结构

函数定义

构造函数
代码语言：javascript复制
template<typename K>
class BSTree
{
    typedef BSNode<K> Node;/*<K>不可以省，类模板必须显示传模板参数*/
public:
    // 无参拷贝构造
    BSTree()
    {}

    // 析构
    void Destory(Node*& root)
    {
        if (root == nullptr)
            return;

        Destory(root->left);
        Destory(root->right);
        delete root;
        root = nullptr;
    }
private:
    Node* _root = nullptr/*初始化，这样子就可以不用在构造时赋值了*/;
};
拷贝构造
代码语言：javascript复制
    BSTree(const BSTree<K>& tree)
    {
        /*
            参数：
            &:减少拷贝，提高效率
            const：避免该函数更改tree的值
        */
        _root = Copy(tree._root);
    }

    Node* Copy(Node* root)
    {
        // 一个树要构造，就需要它的孩子节点构造好 -------------> 所以要使用后序遍历
        if (root == nullptr)
            return nullptr;

        Node* newRoot = new Node(root->key);
        newRoot->left = Copy(root->left);
        newRoot->right = Copy(root->right);
    
        return newRoot;
    }
重载赋值运算符（=）
扩展

C 中提供了重载函数，我们可以重载大部分运算符，这使我们对自定义类型的操作更方便，但如下运算符不可以被重载

  1. . (成员访问运算符): 这个运算符用于访问类、结构体或联合体的成员。由于它用于访问成员变量和成员函数，它的行为是固定的，不能被重载。
  2. .* (成员指针访问运算符): 这个运算符用于通过成员指针访问类的成员。同样，由于它直接关联于类的内部结构，它的行为也是固定的，不允许重载。
  3. :: (作用域解析运算符): 这个运算符用于指定类、命名空间或枚举类型的成员。它用于指定一个特定的作用域中的名称，其意义和作用域在C 中是固定的，因此不能被重载。
  4. sizeof (类型大小运算符): 这个运算符用于获取对象或类型在内存中所占的字节大小。由于sizeof在编译时就被求值，并且其行为与具体的运行时上下文无关，因此它不能被重载。
  5. typeid (类型识别运算符): 这个运算符用于在运行时获取对象的类型信息。虽然它的行为在某些方面依赖于对象本身，但它是语言内置的运行时类型识别机制的一部分，因此不能被重载。
  6. ?: (条件运算符，也称为三元运算符): 虽然这个运算符的行为可以根据给定的条件动态变化，但它是C 语言的一部分，其语法和功能在语言中是固定的，因此不允许被重载。
  7. # 和 ## (预处理运算符): 这两个运算符在预处理阶段用于宏展开和字符串化等操作，与C 的运行时或编译时环境不直接相关，因此它们不被视为C 的运算符，自然也无法被重载。

我们在写代码时，提高复用有时候能提高效率，而下面关于拷贝构造的复用就是一种标选

代码语言：javascript复制
    BSTree<K>& operator=(BSTree tree)
    {
        /*
            参数：拷贝构造 ----------> 方便后序swap
        */

        swap(*this, tree);
        /*
            这样子就可以出了该函数就会自己调用析构函数
        */

        return *this;
        // 返回值传引用的原因：
        // 1、减少拷贝数据的时间，提高效率
        // 2、出了作用域，该返回值仍然存在，所以可以传引用，否则就会崩溃
    }
Insert函数
代码语言：javascript复制
    bool Insert(const K& k)
    {
        // 从根节点查找正确插入位置
        Node* cur = _root;

        // 记录父节点，方便后序插入时操作
        Node* parent = nullptr;    
        // = nullptr更好，如果设置为 = NULL，有时候可能出问题，因为NULL的底层只是数字0被强转为指针，而nullptr是真正的指针
        /*
            底层：
            #ifndef NULL
                #ifdef __cplusplus
                    #define NULL 0
                #else
                    #define NULL ((void *)0)
                #endif
            #endif
        */
    
        // 寻找插入位置，由于二叉排序树的数据都需要插入到叶子节点，所以该处的循环停止条件为cur为nullptr
        while (cur)
        {
            parent = cur;
            if (k < cur->key)
            {
                // 如果查找的值 < 该节点的值，查找左子树
                cur = cur->left;
            }
            else if (k > cur->key)
            {
            // 如果查找的值 > 该节点的值，查找右子树
                cur = cur->right;
            }
            else// 与二叉树中的值相等，在二叉排序树中不可有重复数据，因此返回false
                return false;
        }

        // 处理节点
        Node* node = new Node(k);
        if (parent == nullptr)
            _root = node;
        else if (k > parent->key)
        {
            parent->right = node;
        }
        else
            parent->left = node;
    
        return true;
    }
Erase函数
代码语言：javascript复制
    void Erase(const K& k)
    {
        Node* parent = nullptr;
        Node* cur = _root;

        // 查找该值
        while (cur)
        {
            if (k < cur->key)
            {
                parent = cur;
                cur = cur->left;
            }
            else if (k > cur->key)
            {
                parent = cur;
                cur = cur->right;
            }
            else
            {
                // 讲解
            }
        }
    }

当查找到该值时，我们需要进行复杂的操作才可以删除这个元素

分析
一、该节点左节点为空
1、删除的节点为根

很显然，只需要将根节点改为根节点的右孩子就好

代码语言：javascript复制
if (cur->left == nullptr)
{
    if (cur == _root)
    {
        _root = cur->right;
    }
}
2、该节点不是根节点

（1）它是父节点的左孩子（如下面的1）

我们只需要：

① 父节点的左孩子的指针指向删除元素的右孩子 ② 删除元素的右孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素

（2）它是父节点的右孩子

① 父节点的右孩子的指针指向删除元素的右孩子 ② 删除元素的右孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素

代码语言：javascript复制
    else if (parent->left == cur)
    {
        parent->left = cur->right;
    }
    else if (parent->right == cur)
    {
        parent->right = cur->right;
    }
    
    delete cur;// 删除该节点
二、该节点右节点为空
1、删除的节点为根

很显然，只需要将根节点改为根节点的左孩子就好

代码语言：javascript复制
else if (cur->right == nullptr)
{
    if (cur == _root)
    {
        _root = cur->left;
    }
}
2、该节点不是根节点

（1）它是父节点的左孩子

我们只需要：

① 父节点的左孩子的指针指向删除元素的左孩子 ② 删除元素的左孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素

（2）它是父节点的右孩子

① 父节点的右孩子的指针指向删除元素的左孩子 ② 删除元素的右孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素

代码语言：javascript复制
    else if (parent->left == cur)
    {
        parent->left = cur->left;
    }
    else if (parent->right == cur)
    {
        parent->right = cur->left;
    }
    delete cur;
三、左右孩子都存在

这种情况有两种解决方法

1、找其左子树的最大节点（也就是左子树最右边的节点） 2、找其右子树的最小节点（也就是右子树最左边的节点）

我将用第二种方法举例

1、先将指针指向右子树节点 2、一直向左遍历 3、找到最左边节点 4、与要删除的节点的 值 交换 5、再按照上面的左孩子为空的解决方法，删除该元素

演示

找到最左边节点，将其与要删除的节点的 值 交换

5、再按照上面的左孩子为空的解决方法，删除该元素

代码语言：javascript复制
else
{
    Node* subLeftParent = cur;
    
    // 1、先将指针指向右子树节点
    Node* subLeft = cur->right;
    
    //2、一直向左遍历，找到最左边节点
    while (subLeft->left)
    {
        subLeftParent = subLeft;
        subLeft = subLeft->left;
    }

    // 4、与要删除的节点的 值 交换
    swap(subLeft->key, cur->key);


    // 5、再按照上面的左孩子为空的解决方法，删除该元素
    if (subLeft == subLeftParent->left)
    {
        subLeftParent->left = subLeft->right;
        delete subLeft;
    }
    else
    {
        subLeftParent->right = subLeft->right;
        delete subLeft;
    }
}

// 返回
return;
Find函数
代码语言：javascript复制
bool Find(const K& k)
{
    Node* cur = _root;

    while (cur)
    {
        if (k < cur->key)
        {
            cur = cur->left;
        }
        else if (k > cur->key)
        {
            cur = cur->right;
        }
        else
            return true;
    }

    return false;
}
Inorder中序遍历函数
代码语言：javascript复制
// 因为外界不知道root，所以这样子就省的再写一个函数去获取_root了
void Inorder()
{
    _Inorder(_root);
}

private:
    void _Inorder(Node* root)
    {
        if (root == nullptr)
            return;

        _Inorder(root->left);
        cout << root->key << ' ';
        _Inorder(root->right);
    }

FindR函数（递归查找元素）

代码语言：javascript复制
bool FindR(const K& k)
{
    return _FindR(_root, k);
}

private:
    bool _FindR(Node* root, const K& k)
    {
        if (root == nullptr)
            return false;

        if (k > root->key)
            return _FindR(root->right);
        else if (k < root->key)
            return _FindR(root->left);
        else
            return true;
    }
InsertR函数（递归插入）
代码语言：javascript复制
bool InsertR(const K& k)
{
    return _InsertR(_root, k);
}
private:
    bool _InsertR(Node*& root, const K& k)
    {
        if (root == nullptr)
        {
            // 因为传参是引用，就不需要去记录父节点，而直接改变
            root = new Node(k);
            return true;
        }

        if (k > root->key)
            return _InsertR(root->right, k);
        else if (k < root->key)
            return _InsertR(root->left, k);
        else
            return false;
    }
EraseR函数（递归删除）
代码语言：javascript复制
bool EraseR(const K& k)
{
    return _EraseR(_root, k);
}
private:
    bool _EraseR(Node*& root, const K& k)
    {
        if (root == nullptr)
            return false;

        if (root->key < k)
            return _EraseR(root->right, k);
        else if (root->key > k)
            return _EraseR(root->left, k);
        else
        {
            if (root->left == nullptr)
            {
                Node* del = root;
                root = root->right;
                delete del;
            }
            else if (root->right == nullptr)
            {
                Node* del = root;
                root = root->left;
                delete del;
            }
            else
            {
                // 找右子树最左边的
                Node* subLeft = root->right;
                while (subLeft->left)
                {
                    subLeft = subLeft->left;
                }
                // 更改 右子树最小元素 和 要删除元素 的值
                swap(root->key, subLeft->key);

                /*关键点，因为传的是引用，因此只需要重复“左孩子为空”这种情况的代码就好*/
                return _EraseR(root->right, k);
            }
        }
    }
析构函数
代码语言：javascript复制
~BSTree()
{
    Destory(_root);
}

private:
    Node* Destory(Node*& root)
    {
        if (root == nullptr)
            return nullptr;

        root->left = Destory(root->left);
        root->right = Destory(root->right);
        delete root;
        root = nullptr;
        return nullptr;
    }

总代码

代码语言：javascript复制
#pragma once

										/*二叉搜索树*/

/* k模型 */
// 查看是否存在
namespace key
{
	template<typename K>
	struct BSNode
	{
		BSNode<K>* left;
		BSNode<K>* right;
		K key;

		BSNode(const K& k)
			: left(nullptr)
			, right(nullptr)
			, key(k)
		{}
	};

	template<typename K>
	class BSTree
	{
		typedef BSNode<K> Node;
	public:
		BSTree()
		{}

		BSTree(const BSTree<K>& tree)
		{
			_root = Copy(tree._root);
		}

		BSTree<K>& operator=(BSTree tree)
		{
			swap(*this, tree);
			return *this;
		}

		bool Insert(const K& k)
		{
			Node* parent = nullptr;
			Node* cur = _root;
		
			while (cur)
			{
				parent = cur;
				if (k < cur->key)
				{
					cur = cur->left;
				}
				else if (k > cur->key)
				{
					cur = cur->right;
				}
				else
					return false;
			}

			Node* node = new Node(k);
			if (parent == nullptr)
				_root = node;
			else if (k > parent->key)
			{
				parent->right = node;
			}
			else
				parent->left = node;
		
			return true;
		}

		void Erase(const K& k)
		{
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				// parent = cur;
				// 不可以放在这里

				if (k < cur->key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (k > cur->key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					if (cur->left == nullptr)
					{
						// 根节点，根节点没有父亲
						if (cur == _root)
						{
							_root = cur->right;
						}
						else if (parent->left == cur)
						{
							parent->left = cur->right;
						}
						else if (parent->right == cur)
						{
							parent->right = cur->right;
						}
						delete cur;
					}
					else if (cur->right == nullptr)
					{
						// 根节点，根节点没有父亲
						if (cur == _root)
						{
							_root = cur->left;
						}
						else if (parent->left == cur)
						{
							parent->left = cur->left;
						}
						else if (parent->right == cur)
						{
							parent->right = cur->left;
						}
						delete cur;
					}
					else
					{
						// 找右子树的最左节点
						Node* parent = cur;//注意！！！！！！！要等于cur
						Node* subLeft = cur->right;
						while (subLeft->left)
						{
							parent = subLeft;
							subLeft = subLeft->left;
						}
						swap(subLeft->key, cur->key);

						if (subLeft == parent->left)
						{
							parent->left = subLeft->right;
							delete subLeft;
						}
						else
						{
							parent->right = subLeft->right;
							delete subLeft;
						}
					}

					return;
				}
			}
		}

		bool Find(const K& k)
		{
			Node* cur = _root;

			while (cur)
			{
				if (k < cur->key)
				{
					cur = cur->left;
				}
				else if (k > cur->key)
				{
					cur = cur->right;
				}
				else
					return true;
			}

			return false;
		}

		// 因为外界不知道root，所以这样子就省的再写一个函数去获取_root了
		void Inorder()
		{
			_Inorder(_root);
		}

		bool FindR(const K& k)
		{
			return _FindR(_root, k);
		}

		bool InsertR(const K& k)
		{
			return _InsertR(_root, k);
		}

		bool EraseR(const K& k)
		{
			return _EraseR(_root, k);
		}

		~BSTree()
		{
			Destory(_root);
		}
	private:
		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			_root = new Node(root->key);
			_root->left = Copy(root->left);
			_root->right = Copy(root->right);
		
			return _root;
		}

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

			_Inorder(root->left);
			cout << root->key << ' ';
			_Inorder(root->right);
		}

		bool _FindR(Node* root, const K& k)
		{
			if (root == nullptr)
				return false;

			if (k > root->key)
				return _FindR(root->right);
			else if (k < root->key)
				return _FindR(root->left);
			else
				return true;
		}

		bool _InsertR(Node*&/*这样子就不用记住父节点也能插入*/ root, const K& k)
		{
			if (root == nullptr)
			{
				root = new Node(k);
				return true;
			}

			if (k > root->key)
				return _InsertR(root->right, k);
			else if (k < root->key)
				return _InsertR(root->left, k);
			else
				return false;
		}

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

			if (root->key < k)
				return _EraseR(root->right, k);
			else if (root->key > k)
				return _EraseR(root->left, k);
			else
			{
				if (root->left == nullptr)
				{
					Node* del = root;
					root = root->right;/**/
					delete del;
				}
				else if (root->right == nullptr)
				{
					Node* del = root;
					root = root->left;/**/
					delete del;
				}
				else
				{
					// 找右子树最左边的
					Node* subLeft = root->right;
					while (subLeft->left)
					{
						subLeft = subLeft->left;
					}
					swap(root->key, subLeft->key);

					return _EraseR(root->right, k);/**/
				}
			}
		}

		Node* Destory(Node*& root)
		{
			if (root == nullptr)
				return nullptr;

			root->left = Destory(root->left);
			root->right = Destory(root->right);
			delete root;
			root = nullptr;
		}
	private:
		Node* _root = nullptr;
	};
}

拓展

key、value结构

当为kv结构时，只需将BNTreeNode部分、Insert部分修改就好

结语

该代码使用了一些C 技巧，简述就是一下部分，若大家回想不起来可以去相关代码地方去看哦

1、传参为引用 和 拷贝 的灵活使用

【注】 当为引用时：减少拷贝时间，提高效率 当为拷贝时：对于重载=这种运算符时，可以及时销毁临时变量

2、返回值为引用 和 拷贝 的灵活使用

【注】 使用引用返回的场景：出了该作用域该对象仍然存在

3、了解NULL的底层，为什么nullptr好

【注】 NULL的底层实际是对数字0的强转指针的define，有时候容易出问题，所以我们尽量使用nullptr

4、提供给外部的接口种调用内部接口的原因

【注】 外部无法得知内部消息（如二叉搜索树的根节点），这样子可以用外部接口中调用内部接口就会方便很多，也不需要专门写一堆用来获取内部属性的接口（如该代码的GetRoot这种函数）

好啦~~，到这里就圆满结束啦，恭喜你今天又进步了一点点哦ε=ε=ε=(~￣▽￣)~，如果对我的文章较为满意的话，欢迎点赞收藏和关注哦，后续我将更新《AVL树》《红黑树》《STL的模拟实现》部分，敬请期待哦

函数 搜索 指针 root 遍历

0 人点赞