【C++】深入拆解二叉搜索树：从递归与非递归双视角，彻底掌握STL容器的基石

#include<iostream>
using namespace std;

namespace dh
{
	//模板声明，K为节点中存储的键值类型
	template<class K>
	//定义节点结构体
	struct BinarySearchTreeNode
	{
		//将这个节点结构体模板重命名（更简洁）
		typedef BinarySearchTreeNode<K> BSTNode;

		BSTNode* _left;//指向左子节点指针
		BSTNode* _right;//指向右子节点指针
		K _key;
		// 构造函数：初始化节点，键值为传入的 key，左右子节点初始化为空
		BinarySearchTreeNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{ }
	};
	

	//模板声明，与节点键值类型保持一致
	template<class K>
	//二叉搜索树类
	class BinarySearchTree
	{
	public:
		// 在树类内部定义节点别名（简化访问）
		typedef BinarySearchTreeNode<K> BSTNode;

		//构造函数：初始化树为空树
		BinarySearchTree()
			:_root(nullptr)
		{ }
			private:
		//树的根节点（整个树的入口）
		BSTNode* _root;
	};
}

	//判断树是否为空并执行相应操作
	bool Insert(const K& key)
	{
		if (_root == nullptr) { _root = new BSTNode(key); }
		else
		{
			BSTNode* parent = nullptr;//记录父节点
			BSTNode* cur = _root;//从根节点开始比较遍历
			while (cur != nullptr)
			{
				if (key > cur->_key)
				{
					parent = cur;//更新父节点
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;//更新父节点
					cur = cur->_left;
				}
				else
				{
					return false;//如果插入键值相同返回错误
				}
			}
			if (key > parent->_key) { parent->_right = new BSTNode(key); }
			else { parent->_left = new BSTNode(key); }
		}

		return true;
	}

//查找函数
bool Find(const K& key)
{
	BSTNode* cur = _root;
	while (cur != nullptr)
	{
		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)
{
	BSTNode* parent = nullptr;
	BSTNode* cur = _root;
	while (cur != nullptr)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//查找到需要删除的节点
		else
		{
			//目标节点的右孩子为空
			if (cur->_right == nullptr)
			{
				//目标节点的父节点为空，目标节点是根节点，删除后它的左孩子变成新的根
				if (parent == nullptr) { _root = cur->_left; }
				//目标节点不是根节点
				else
				{
					//目标节点是父节点的右孩子
					if (key > parent->_key) { parent->_right = cur->_left; }
					//目标节点是父节点的左孩子
					else { parent->_left = cur->_left; }
				}
			}
			//目标节点的左孩子为空
			else if (cur->_left == nullptr)
			{
				//cur是根节点
				if (parent == nullptr) { _root = cur->_right; }
				//cur不是根节点
				else
				{
					//目标节点是父节点的右孩子
					if (key > parent->_key) { parent->_right = cur->_right; }
					//目标节点是父节点的左孩子
					else { parent->_left = cur->_right; }
				}
			}
			//左右子节点均存在(这里采用左子树最大节点替换法)
			//这里的最大节点只有两种可能：
			//没有节点 有一个左子节点 不可能有右子节点
			else
			{
				BSTNode* SubMaxParent = cur;
				BSTNode* SubMax = cur->_left;
				//查找到左子树最大节点和它的父节点
				while (SubMax->_right != nullptr)
				{
					SubMaxParent = SubMax;
					SubMax = SubMax->_right;
				}
				//把SubMax赋值给目标节点(进行替换)
				cur->_key = SubMax->_key;
				//进行删除
				//如果SubMaxParent是cur，说明submax是cur的直接左孩子
				if (SubMaxParent == cur) { SubMaxParent->_left = SubMax->_left; }
				//submax是submaxparent的右孩子
				else { SubMaxParent->_right = SubMax->_left; }

				//转移删除节点指针的目标
				cur = SubMax;
			}

			delete cur;
			return true;
		}
	}
	return false;
}

public:
		// 1. 公有接口函数（类外调用入口）
		void InOrder()
		{
			// 空树直接返回，调用私有子遍历函数并传入根节点
			_InOrder(_root);
		}
private:
			//树的根节点（整个树的入口）
			BSTNode* _root;

			// 2. 私有子遍历函数（负责递归逻辑）
			void _InOrder(BSTNode* cur)
			{
				// 递归终止：当前节点为空，无需遍历
				if (cur == nullptr)
					return;

				// 中序遍历：左→根→右
				_InOrder(cur->_left);    // 先遍历左子树
				cout << cur->_key << " "; // 访问当前节点（可替换为其他处理逻辑）
				_InOrder(cur->_right);   // 再遍历右子树
			}

public:
    // 递归插入接口：对外提供的插入入口
    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);  // 调用私有递归子函数
    }

private:
    // 递归插入子函数：实际执行插入逻辑（私有，仅内部调用）
    // 参数 root：当前节点的指针引用，用于直接修改父节点的左/右孩子
    bool _Insert(BSTNode*& root, const K& key)
    {
        if (root == nullptr)  // 找到插入位置（空节点）
        {
            root = new BSTNode(key);  // 创建新节点并通过引用绑定到父节点
            return true;
        }
        // 根据key大小递归查找插入位置
        if (key > root->_key)
            return _Insert(root->_right, key);  // 插入右子树
        else if (key < root->_key)
            return _Insert(root->_left, key);   // 插入左子树
        else
            return false;  // key已存在，插入失败
    }

//递归查找
public:
    // 递归查找接口：对外提供的查找入口
    bool FindR(const K& key)
    {
        return _FindR(_root, key);  // 调用私有递归子函数
    }

private:
    // 递归查找子函数：实际执行查找逻辑（私有，仅内部调用）
    // 参数 root：当前节点的const指针引用（避免修改节点，提高安全性）
    bool _FindR(const BSTNode*& root, const K& key)
    {
        if (root == nullptr)  // 递归终止条件：节点为空，未找到key
            return false;
        
        // 根据BST特性递归查找
        if (key > root->_key)
            return _FindR(root->_right, key);  // 去右子树查找
        else if (key < root->_key)
            return _FindR(root->_left, key);   // 去左子树查找
        else
            return true;  // 找到匹配key
    }

public:
	//递归删除
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:
		//递归删除节点子函数
		bool _EraseR( BSTNode*& 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
			{
				//先储存根节点的值，避免修改root丢失地址
				BSTNode* delNode = root;
				//有一方为空子树的场景
				if (root->_right == nullptr)
				{
					root = root->_left;
					delete delNode;
					return true;
				}
				else if (root->_left == nullptr)
				{
					root = root->_right;
					delete delNode;
					return true;
				}
				//左右都有子树的情景
				else
				{
					BSTNode* subMAX = root->_left;
					while (subMAX->_right)
					{
						subMAX = subMAX->_right;
					}

					root->_key = subMAX->_key;
					return _EraseR(root->_left, subMAX->_key);
				}
			}
		}