/** * 目的：实现AVL * 利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合acm模板 * 其实avl在acm中基本不用，基本被treap取代 * avl一般只要求理解思路，不要求写出代码，因为真心很烦 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <time.h> #include <queue> using namespace std; int COUNT; //统计树中不重复节点的个数 int HEIGHT; //统计数的高度 //数据节点 class DNode { public:  int data;  DNode():data(0){};  DNode(int d):data(d){}  bool operator = (const DNode &d){   return data = d.data;  }  bool operator == (const DNode &d){   return data == d.data;  }  bool operator > (const DNode &d){   return data > d.data;  }  bool operator < (const DNode &d){   return data < d.data;  }  void show(){   cout << endl;   cout << "***************" << endl;   cout << "data: " << data << endl;  } }; //treap的节点 template<class T> class AVLNode{ private:  int hgt; //节点的高度 public:  T data;  int count;  AVLNode<T> *son[2]; //0是左儿子，1是右儿子  AVLNode<T>(T data):data(data), count(1){   son[0] = son[1] = NULL;   hgt = 1;  }  int max(int a, int b){return a > b ? a : b;}  void show(){   data.show();   cout << "c hgt: " << this->height() << endl;   cout << "l hgt: " << this->son[0]->height() << endl;   cout << "r hgt: " << this->son[1]->height() << endl;   cout << "count: " << count << endl;   cout << endl;  }  int height(){   if(NULL == this)    return 0;   return _getHeight(this);  }  int _getHeight(AVLNode<T> * cur){   if(NULL == cur)    return 0;   return 1 + max(_getHeight(cur->son[0]), _getHeight(cur->son[1]));  }  void setHeight(){   hgt = _getHeight(this);  } }; //AVL Tree //这里的T是节点中的数据类型 template<class T> class AVLTree{ private:  AVLNode<T> * root;  //根节点  int hgt;   //树的高度  int size;   //树中不重复节点数量  void _insert(AVLNode<T> *& cur, T data);  void _mid_travel(AVLNode<T> *cur);  //层次遍历  void _cengci_travel(AVLNode<T> *cur);  //单旋转（左左，右右）, 左旋不是想左旋转的意思， 而是由于左子树的左儿子的高度太大  //与treap的旋转命名相反  void _singleRoate(AVLNode<T> *& cur, int dir);  //双旋转（两次单旋转）  void _doubleRoate(AVLNode<T> *& cur, int dir);  int max(int a, int b){   return a > b ? a : b;  } public:  AVLTree():root(NULL), hgt(0){}  void insert(const T & data);  void mid_travel();  int height(){   return root->height();  }  //层次遍历  void cengci_travel(){   _cengci_travel(root);  }; }; /*************  私有方法开始**********************/ template<class T> void AVLTree<T>::_insert(AVLNode<T> *& cur, T data){  if(NULL == cur){   cur = new AVLNode<T>(data);  }else if(data == cur->data){   cur->count++;  }else{   int dir = (data > cur->data);   _insert(cur->son[dir], data);   if(2 <= cur->son[dir]->height() - cur->son[!dir]->height()){    bool lr = (data > cur->data);    lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir);   }  }  cur->setHeight();  //cout << "set height: " << endl;  //cur->show(); } template<class T> void AVLTree<T>::_mid_travel(AVLNode<T> * cur){  if(NULL != cur){   //先查找做子树   _mid_travel(cur->son[0]);   //if(abs(cur->son[0]->height() - cur->son[1]->height()) >= 2)   {    cur->show();   }   _mid_travel(cur->son[1]);  } } //层次遍历， //如果节点为空就输出0 来占位 template<class T> void AVLTree<T>::_cengci_travel(AVLNode<T> * cur){  if(NULL == cur)   return;  queue<AVLNode<T>*> q;  q.push(cur);  AVLNode<T> *top = NULL;  queue<AVLNode<T>*> tmp;  while(!q.empty()){   while(!q.empty()){    top = q.front();    q.pop();    if(NULL == top){     //用#代表该节点是空，#的后代还是#     cout << '#' << " ";     tmp.push(top);    }else{     cout << top->data.data << " ";     tmp.push(top->son[0]);     tmp.push(top->son[1]);    }   }   bool flag = false;   while(!tmp.empty()){    if(NULL != tmp.front())     flag = true;    q.push(tmp.front());    tmp.pop();   }   cout << endl;   if(!flag)    break;  } } //单旋转，即只旋转一次 //dir = 0时,左左旋转；否则为右右旋转 template<class T> void AVLTree<T>::_singleRoate(AVLNode<T> *& cur, int dir){  AVLNode<T> *& k2 = cur, * k1 = k2->son[dir]; //k2 必须是引用  k2->son[dir] = k1->son[!dir];  k1->son[!dir] = k2;  k2 = k1;  k2->setHeight();  k1->setHeight(); } //双旋转，即调两次单旋转 //dir = 0是左右情况； 否则为右左情况 template<class T> void AVLTree<T>::_doubleRoate(AVLNode<T> *& cur, int dir){  _singleRoate(cur->son[dir], !dir);  _singleRoate(cur, dir); } /*************  公有方法（接口）开始**********************/ template<class T> void AVLTree<T>::insert(const T & data){  _insert(root, data); } template<class T> void AVLTree<T>::mid_travel(){  _mid_travel(root); } int main(){  AVLTree<DNode>* avlt = new AVLTree<DNode>();  const int num = 30;  for(int i = 0; i < num; i++){   DNode * d = new DNode(i);   avlt->insert(*d);  }  cout << "*************中序遍历***************" << endl;  avlt->mid_travel();  cout << "**************中序遍历结束**********" << endl;  cout << "*************层次遍历开始***************" << endl;  avlt->cengci_travel();  cout << "**************层次遍历结束**********" << endl;  cout << "树的高度是： " << avlt->height() << endl;  return 0; }