#include <iostream> #include <algorithm> #include <queue> template <typename T> class AVLTree { private: struct Node { T data; Node* left; Node* right; int height; Node(const T& val) : data(val), left(nullptr), right(nullptr), height(1) {} }; Node* root; // 获取节点高度 int getHeight(Node* node) { return node ? node->height : 0; } // 更新节点高度 void updateHeight(Node* node) { if (node) { node->height = 1 + std::max(getHeight(node->left), getHeight(node->right)); } } // 获取平衡因子 int getBalanceFactor(Node* node) { return node ? getHeight(node->left) - getHeight(node->right) : 0; } // 右旋 Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; updateHeight(y); updateHeight(x); return x; } // 左旋 Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; updateHeight(x); updateHeight(y); return y; } // 平衡节点 Node* balance(Node* node) { if (!node) return nullptr; updateHeight(node); int balanceFactor = getBalanceFactor(node); // 左左情况 if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0) { return rightRotate(node); } // 右右情况 if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0) { return leftRotate(node); } // 左右情况 if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) { node->left = leftRotate(node->left); return rightRotate(node); } // 右左情况 if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // 插入辅助函数 Node* insert(Node* node, const T& val) { if (!node) return new Node(val); if (val < node->data) { node->left = insert(node->left, val); } else if (val > node->data) { node->right = insert(node->right, val); } else { return node; // 重复值不插入 } return balance(node); } // 找到最小值节点 Node* findMin(Node* node) { while (node && node->left) { node = node->left; } return node; } // 删除辅助函数 Node* remove(Node* node, const T& val) { if (!node) return nullptr; if (val < node->data) { node->left = remove(node->left, val); } else if (val > node->data) { node->right = remove(node->right, val); } else { // 找到要删除的节点 if (!node->left || !node->right) { Node* temp = node->left ? node->left : node->right; if (!temp) { temp = node; node = nullptr; } else { *node = *temp; } delete temp; } else { // 有两个子节点，找到右子树的最小节点 Node* temp = findMin(node->right); node->data = temp->data; node->right = remove(node->right, temp->data); } } if (!node) return nullptr; return balance(node); } // 查找辅助函数 bool contains(Node* node, const T& val) const { if (!node) return false; if (val < node->data) return contains(node->left, val); if (val > node->data) return contains(node->right, val); return true; } // 释放内存 void clear(Node* node) { if (node) { clear(node->left); clear(node->right); delete node; } } // 中序遍历辅助函数 void inorder(Node* node, std::vector<T>& result) const { if (!node) return; inorder(node->left, result); result.push_back(node->data); inorder(node->right, result); } public: AVLTree() : root(nullptr) {} ~AVLTree() { clear(root); } // 插入元素 void insert(const T& val) { root = insert(root, val); } // 删除元素 void remove(const T& val) { root = remove(root, val); } // 查找元素 bool contains(const T& val) const { return contains(root, val); } // 清空树 void clear() { clear(root); root = nullptr; } // 判断是否为空 bool empty() const { return root == nullptr; } // 获取高度 int height() const { return getHeight(root); } // 中序遍历 std::vector<T> inorder() const { std::vector<T> result; inorder(root, result); return result; } // 层序遍历 (用于测试) void levelOrder() const { if (!root) return; std::queue<Node*> q; q.push(root); while (!q.empty()) { Node* current = q.front(); q.pop(); std::cout << current->data << "(" << current->height << ") "; if (current->left) q.push(current->left); if (current->right) q.push(current->right); } std::cout << std::endl; } }; // 测试代码 int main() { AVLTree<int> tree; // 插入测试 tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(40); tree.insert(50); tree.insert(25); std::cout << "Level order traversal after insertion:" << std::endl; tree.levelOrder(); // 查找测试 std::cout << "Contains 30: " << (tree.contains(30) ? "Yes" : "No") << std::endl; std::cout << "Contains 35: " << (tree.contains(35) ? "Yes" : "No") << std::endl; // 删除测试 tree.remove(30); std::cout << "Level order traversal after deletion of 30:" << std::endl; tree.levelOrder(); // 中序遍历测试 auto inorder = tree.inorder(); std::cout << "Inorder traversal: "; for (int num : inorder) { std::cout << num << " "; } std::cout << std::endl; return 0; }