#include <iostream> using namespace std; //AVL树的节点 template<typename T> class TreeNode { public: TreeNode() :lson(NULL), rson(NULL), freq(1), hgt(0){} T data;//值 int hgt;//以这个结点为根的树的高度 int freq;//相同点的频率，我是不知道 TreeNode* lson, *rson;//左右儿子的地址 }; template<typename T> class AVLTree {//AVLTree的类属性和方法声明 private: TreeNode<T>*root;//根节点 void insertpri(TreeNode<T>*&node, T x);//插入 TreeNode<T>* findpri(TreeNode<T>* node, T x);//查找 void traversalpri(TreeNode<T>* node);//遍历 void delpri(TreeNode<T>* &node, T x);//删除 int height(TreeNode<T>* node);//辅助操作：高度 void singLeft(TreeNode<T>* &k2);//左左操作 void singRight(TreeNode<T>* &k2);//右右操作 void doubleLeft(TreeNode<T>* &k3);//左右操作 void doubleRight(TreeNode<T>* &k3);//右左操作 int max(int cmpa, int cmpb); public: AVLTree() :root(NULL){}; void insert(T x);//插入接口 void del(T x);//删除接口 TreeNode<T>* find(T x);//查找接口 void traversal();//遍历接口 }; //辅助操作：高度 template<typename T> int AVLTree<T>::height(TreeNode<T>* node) { if (node!=NULL) return node->hgt; return -1; } //辅助操作：比较高度 template<typename T> int AVLTree<T>::max(int cmpa, int cmpb) { return cmpa > cmpb ? cmpa : cmpb; } template<typename T> void AVLTree<T>::singLeft(TreeNode<T>* &k2) {//左左情况下旋转 TreeNode<T>* k1; k1 = k2->lson; k2->lson = k1->rson; k1->rson = k2; k2 = k1; k2->hgt = max(height(k2->lson), height(k2->rson))+1; k1->hgt = max(height(k1->lson), height(k1->rson))+1; } template<typename T> void AVLTree<T>::singRight(TreeNode<T>* &k2) {//左左情况下旋转 TreeNode<T>* k1; k1 = k2->rson; k2->rson = k1->lson; k1->lson = k2; k2 = k1; k2->hgt = max(height(k2->lson), height(k2->rson))+1; k1->hgt = max(height(k1->lson), height(k1->rson))+1; } template<typename T> void AVLTree<T>::doubleLeft(TreeNode<T>* &k3) {//左右的情况 singRight(k3->lson); singLeft(k3); } //右左的情况 template<typename T> void AVLTree<T>::doubleRight(TreeNode<T>* &k3) { singLeft(k3->rson); singRight(k3); } //插入 template<typename T> void AVLTree<T>::insertpri(TreeNode<T>* &node, T x) { if (node == NULL) { node = new TreeNode<T>(); node->data = x; return; } if (node->data>x) { insertpri(node->lson, x);//递归插入 //插入后自我调整 if (2 == height(node->lson) - height(node->rson)) if (node->lson->data < x) doubleRight(node); else singLeft(node); } else if (node->data < x) { insertpri(node->rson, x); if (2 == height(node->rson) - height(node->lson)) if (node->rson->data < x) singRight(node); else doubleRight(node); } else ++(node->freq); //取新的高度值，后面的+1很重要，作者都忘记了加 node->hgt = max(height(node->lson), height(node->rson)) + 1; } //插入接口 template<typename T> void AVLTree<T>::insert(T x) { insertpri(root, x); } //查找 template<typename T> TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node, T x) { if (node == NULL) return NULL; if (node->data > x) return findpri(node->lson, x); else if (node->data < x) return findpri(node->rson, x); else return node; } //查找 template<typename T> TreeNode<T>* AVLTree<T>::find(T x) { findpri(root, x); } //删除 template<typename T> void AVLTree<T>::delpri(TreeNode<T>* &node,T x) { if (node == NULL) return; if (x < node->data) { delpri(node->lson, x); //删除后的调整 if (2 == height(node->rson) - height(node->lson)) if (node->rson->lson&&height(node->rson->lson) > height(node->rson->rson)) doubleRight(node); else singRight(node); } else if (x > node->data) { delpri(node->rson, x); if (2 == height(node->lson) - height(node->rson)) if (node->lson->rson&&height(node->lson->rson) > height(node->lson->lson)) doubleLeft(node); else singLeft(node); } else//找到后的操作 {//先是有两个儿子的情况 if (node->lson&&node->rson) { TreeNode<T>* t = node->lson; for (; t->rson; t = t->rson); node->data = t->data; node->freq = t->freq; //递归到一个儿子或没有儿子的情况 delpri(node->lson, t->data); if (2 == height(node->rson) - height(node->lson)) {//下面的if自己不会写 if (node->rson->lson&&height(node->rson->lson) > height(node->rson->rson)) doubleRight(node); else singRight(node); } } else { TreeNode<T>* t = node; if (node->lson == NULL) node = node->rson; else if (node->rson == NULL) node = node->lson; delete(t); t = NULL; } } if (node == NULL)return;//表示只有根节点，删了之后就没有了 node->hgt = max(height(node->lson), height(node->rson)); return; } template<typename T> void AVLTree<T>::del(T x) { delpri(root, x); } //中序遍历函数 template<class T> void AVLTree<T>::traversalpri(TreeNode<T>* node) { if (node == NULL) return; traversalpri(node->lson);//先遍历左子树 cout << node->data << " ";//输出根节点 traversalpri(node->rson);//再遍历右子树 } //中序遍历接口 template<class T> void AVLTree<T>::traversal() { traversalpri(root); } int main() { AVLTree<int> t; t.insert(3); t.insert(2); t.insert(1); t.insert(4); t.insert(5); t.insert(0); t.del(2); t.insert(2); t.traversal(); }