C++探索之旅：打造高效二叉搜索树的奥秘与实践

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)
	{}
    
    // 成员函数...
private:
	Node* _root;
};

bool Insert(const K& key) {
    // 如果树为空，则将新节点作为根节点插入
    if (!_root) {
        _root = new Node(key); // 创建根节点
        return true;  // 插入成功
    }

    Node* cur = _root;  // 当前节点从根节点开始
    Node* parent = nullptr;  // 父节点初始化为空

    // 查找插入位置
    while (cur) {
        if (cur->_key < key) {  // 如果插入值比当前节点值大，进入右子树
            parent = cur;  // 更新父节点
            cur = cur->right;  // 继续向右子树遍历
        }
        else if (cur->_key > key) {  // 如果插入值比当前节点值小，进入左子树
            parent = cur;  // 更新父节点
            cur = cur->left;  // 继续向左子树遍历
        }
        else {
            return false;  // 如果插入值已存在，返回 false
        }
    }

    // 此时，cur 为 nullptr，parent 为最后访问的非空节点
    cur = new Node(key);  // 创建新节点

    // 判断将新节点插入到父节点的左子树还是右子树
    if (parent->_key < key) {
        parent->right = cur;  // 插入到父节点的右子树
    }
    else {
        parent->left = cur;  // 插入到父节点的左子树
    }
    
    return true;  // 插入成功
}

public:
    // 对外暴露的插入接口，调用递归的私有插入函数
    bool Insert(const K& key) {
        // 调用私有的递归插入函数，从根节点开始递归插入
        return _Insert(_root, key);
    }
private:
    // 私有的递归插入函数
    // root：当前递归到的节点，key：要插入的值
    bool _Insert(Node*& root, const K& key) {
        // 递归的基本情况：当前子树为空，直接在此位置插入新节点
        if (!root) {
            root = new Node(key);  // 创建新节点并插入
            return true;  // 插入成功
        }

        // 如果插入值大于当前节点的值，则递归进入右子树
        if (root->_key < key) {
            return _Insert(root->right, key);
        }
        // 如果插入值小于当前节点的值，则递归进入左子树
        else if (root->_key > key) {
            return _Insert(root->left, key);
        }
        // 如果值相等，表示节点已经存在，返回 false 表示插入失败
        else {
            return false;
        }
    }

bool Find(const K& key) {
    Node* cur = _root;  // 从根节点开始查找

    // 使用 while 循环遍历树
    while (cur) {
        // 如果当前节点的键值小于目标值，进入右子树查找
        if (cur->_key < key) {
            cur = cur->right;
        }
        // 如果当前节点的键值大于目标值，进入左子树查找
        else if (cur->_key > key) {
            cur = cur->left;
        }
        // 如果当前节点的键值等于目标值，查找成功，返回 true
        else {
            return true;
        }
    }

    // 如果遍历完树都没有找到目标值，返回 false
    return false;
}

public:
    // 对外的接口，启动递归查找操作
    bool Find(const K& key) {
        return _Find(_root, key);
    }
private:
    // 递归查找函数
    bool _Find(Node* root, const K& key) {
        // 基本情况：如果当前节点为空，表示没找到，返回 false
        if (!root) return false;

        // 如果当前节点的值小于目标值，则递归查找右子树
        if (root->_key < key) {
            return _Find(root->right, key);
        }
        // 如果当前节点的值大于目标值，则递归查找左子树
        else if (root->_key > key) {
            return _Find(root->left, key);
        }
        // 如果当前节点的值等于目标值，说明找到了，返回 true
        else {
            return true;
        }
    }

public:
	void InOrder(){
		_InOrder(_root);
		cout << endl;
	}
private:
	void _InOrder(Node* root) const {
		if (!root) return;

		_InOrder(root->left);
		cout << root->_key << " ";
		_InOrder(root->right);
	}

// 定义一个函数，用于删除二叉搜索树中的指定键值，返回是否成功删除  
bool Erase(const K& key){  
    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; // 向左子树移动  
        }  
        else { // 找到了要删除的节点  
            // 左子树为空的情况  
            if (!cur->left) {  
                if (cur == _root) { // 如果当前节点是根节点  
                    _root = cur->right; // 让右子树成为新的根节点  
                }  
                else { // 否则，根据当前节点是父节点的左孩子还是右孩子来更新父节点的子节点  
                    if (parent->right == cur)  
                        parent->right = cur->right;  
                    else  
                        parent->left = cur->right;  
                }  
            }  
            // 右子树为空的情况  
            else if (!cur->right) {  
                if (cur == _root) { // 如果当前节点是根节点  
                    // 注意这里应该是 _root = cur->left; 而不是 _root = cur->right;  
                    _root = cur->left; // 让左子树成为新的根节点  
                }  
                else { // 否则，根据当前节点是父节点的左孩子还是右孩子来更新父节点的子节点  
                    if (parent->right == cur)  
                        parent->right = cur->left;  
                    else  
                        parent->left = cur->left;  
                }  
            }  
            // 左右子树都不为空的情况  
            else {  
                // 找到左子树中的最大节点（即左子树的最右节点）  
                Node* leftmax_parent = cur;  
                Node* leftmax = cur->left;  
                while (leftmax->right) {  
                    leftmax_parent = leftmax;  
                    leftmax = leftmax->right;  
                }  
  
                // 将左子树的最大节点的键值替换为要删除的节点的键值  
                swap(cur->_key, leftmax->_key);  
  
                // 删除左子树中的最大节点（此时它已经移动到了要删除节点的位置）  
                if (leftmax_parent->left == leftmax) {  
                    leftmax_parent->left = leftmax->left;  
                }  
                else {  
                    leftmax_parent->right = leftmax->left; // 注意这里应该是leftmax的左子节点，因为leftmax没有右子节点  
                  
                }  
  
                // 注意：此时cur已经指向了被替换的节点（即左子树中的最大节点），但这个节点现在是要被删除的节点  
                // 因此，下面的delete操作实际上删除的是左子树中的最大节点（其键值已被替换到原要删除的节点上）  
                // 理论上，我们不需要再次对cur进行操作，因为cur的键值已经被替换，并且其物理位置（即内存地址）将在下面的delete中被释放  
                // 但为了代码的清晰性和一致性，这里保留cur = leftmax;虽然在实际执行到delete前，cur的值已经不再重要  
                cur = leftmax;  
            }  
  
            delete cur; // 释放要删除节点的内存  
            return true; // 返回删除成功  
        }  
    }  
  
    return false; // 如果没有找到要删除的键值，返回删除失败  
}

public:  
    // 公共接口，用于从二叉搜索树中删除指定键值的节点  
    bool Erase(const K& key) {  
        return _Erase(_root, key); // 调用私有递归函数来执行删除操作  
    }  
  
private:  
    // 私有递归函数，用于从以root为根的子树中删除指定键值的节点  
    bool _Erase(Node*& root, const K& key) {  
        if (!root) { // 如果当前节点为空，说明键值不存在于树中  
            return false; // 返回删除失败  
        }  
        if (root->_key < key) { // 如果当前节点的键值小于要删除的键值  
            return _Erase(root->right, key); // 在右子树中继续查找并删除  
        }  
        else if (root->_key > key) { // 如果当前节点的键值大于要删除的键值  
            return _Erase(root->left, key); // 在左子树中继续查找并删除  
        }  
        else { // 找到了要删除的节点  
            Node* del = root; // 保存要删除的节点  
  
            // 1. 左子树为空，用右子树替换当前节点  
            if (!root->left) {  
                root = root->right; // 右子树成为新的子树根节点  
            }  
            // 2. 右子树为空，用左子树替换当前节点  
            else if (!root->right) {  
                root = root->left; // 左子树成为新的子树根节点  
            }  
            // 3. 左右子树都不为空，找到左子树中的最大节点（或右子树中的最小节点）  
            //    并将其键值替换到当前节点，然后删除那个最大（或最小）节点  
            else {  
                Node* leftmax = root->left; // 从左子树开始查找最大节点  
                while (leftmax->right) { // 找到左子树中最右边的节点  
                    leftmax = leftmax->right;  
                }  
  
                // 交换当前节点和左子树中最大节点的键值  
                swap(root->_key, leftmax->_key);
				return _Erase(root->left, key);
			}

			delete del;
			return true;
		}
	}

// BSTree类的公有析构函数  
public:  
	~BSTree() {  
		// 调用私有辅助函数Destroy来递归地销毁整棵树  
		Destroy(_root);  
	}  
  
// BSTree类的私有辅助函数，用于递归地销毁整棵树  
private:  
	void Destroy(Node*& root) {  
		// 如果当前节点为空，则直接返回，不执行任何操作  
		if (!root) return;  
  
		// 递归地销毁左子树  
		Destroy(root->left);  
		  
		// 递归地销毁右子树  
		Destroy(root->right);  
		  
		// 删除当前节点，并释放其占用的内存  
		delete root;  
	}

// BSTree类的公有拷贝构造函数  
// 它接受一个同类型的常量引用作为参数，用于初始化新创建的对象  
public:  
	BSTree(const BSTree<K>& t) {  
		// 调用私有辅助函数Copy来递归地复制源树的所有节点  
		_root = Copy(t._root);  
	}  
  
// BSTree类的私有辅助函数，用于递归地复制整棵树  
private:  
	Node* Copy(Node* root) {  
		// 如果当前节点为空，则返回nullptr，表示该子树不需要复制  
		if (!root) return nullptr;  
  
		// 为当前节点创建一个新的副本，并复制其键值  
		Node* copyroot = new Node(root->_key);  
		  
		// 递归地复制左子树，并将复制后的根节点指针赋给新节点的左子节点指针  
		copyroot->left = Copy(root->left);  
		  
		// 递归地复制右子树，并将复制后的根节点指针赋给新节点的右子节点指针  
		copyroot->right = Copy(root->right);  
		  
		// 返回新创建的节点的指针，作为当前子树的根节点  
		return copyroot;  
	}

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

namespace key_value {
	template<class K, class V>
	struct BSTreeNode {
		BSTreeNode<K, V>* left;
		BSTreeNode<K, V>* right;
		K _key;
		V _value;

		BSTreeNode(const K& key, const V& value)
			:left(nullptr)
			,right(nullptr)
			,_key(key)
			,_value(value)
		{}
	};

	template<class K, class V>
	class BSTree {
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		// 递归插入
		bool Insert(const K& key, const V& value) {
			return _Insert(_root, key, value);
		}

		// 递归查找
		Node* Find(const K& key) {
			return _Find(_root, key);
		}

		// 递归调用删除
		bool Erase(const K& key) {
			return _Erase(_root, key);
		}

		// 递归调用中序遍历
		void InOrder() {
			_InOrder(_root);
			cout << endl;
		}

	private:
		bool _Erase(Node*& root, const K& key) {
			if (!root) return false;
			if (root->_key < key) return _Erase(root->right, key);
			else if (root->_key > key) return _Erase(root->left, key);
			else {
				Node* del = root;
				// 1.左为空
				if (!root->left) root = root->right;
				// 2.右为空
				else if (!root->right) root = root->left;
				// 3.左右都不为空
				else {
					Node* leftmax = root->left;
					while (leftmax->right) {
						leftmax = leftmax->right;
					}

					swap(root->_key, leftmax->_key);
					return _Erase(root->left, key);
				}

				delete del;
				return true;
			}
		}

		bool _Insert(Node*& root, const K& key, const V& value) {
			if (!root) {
				root = new Node(key, value);
				return true;
			}

			if (root->_key < key) return _Insert(root->right, key, value);
			else if (root->_key > key) return _Insert(root->left, key, value);
			else return false;
		}

		Node* _Find(Node* root, const K& key) {
			if (!root) return nullptr;
			if (root->_key < key) return _Find(root->right, key);
			else if (root->_key > key) return _Find(root->left, key);
			else return root;
		}

		void _InOrder(Node* root) {
			if (!root) return;

			_InOrder(root->left);
			cout << root->_key << ":" << root->_value << " ";
			_InOrder(root->right);
		}

	private:
		Node* _root;
	};

	void TestBSTree1() {
		BSTree<string, string> dict;
		dict.Insert("insert", "插入");
		dict.Insert("sort", "排序");
		dict.Insert("right", "右边");
		dict.Insert("date", "日期");

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

	void TestBSTree2() {
		// 统计水果出现的次数
		string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr) {
			auto ret = countTree.Find(str);
			if (!ret) countTree.Insert(str, 1);
			else ret->_value++;
		}

		countTree.InOrder();
	}
}