平衡二叉树AVL操作模板模板

1、平衡二叉树AVL操作模板这篇文章主要介绍了平衡二叉树 AVL 操作模板 ,需要的朋友可以参考下复制代码 代码如下 :/* 目的：实现 AVL* 利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合* 其实 avl 在 acm 中基本不用，基本被treap 取代acm 模板* avl 一般只要求理解思路，不要求写出代码，因为真心很烦*/#include #include #include #include #include #include #include using namespace std;int COUNT; / 统计树中不重复节点的个数int HEIGHT; / 统计数的高

2、度/ 数据节点class DNodepublic: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

3、* endl;cout data: data endl;/treap的节点templateclass AVLNodeprivate:int hgt; / 节点的高度public:T data; int count;AVLNode *son2; / 0 是左儿子， 1 是右儿子AVLNode(T data):data(data), count(1)son0 = son1 = NULL;hgt = 1;int max(int a, int b)return a b ? a : b;void show()data.show();cout c hgt: height() endl;cout l hgt

4、: son0-height() endl;cout r hgt: son1-height() endl;cout count: count endl;cout endl;int height()if(NULL = this)return 0;return _getHeight(this);int _getHeight(AVLNode * cur)if(NULL = cur)return 0;return 1 + max(_getHeight(cur-son0), _getHeight(cur-son1);void setHeight()hgt = _getHeight(this);/AVL T

5、ree/ 这里的 T 是节点中的数据类型templateclass AVLTreeprivate:AVLNode * root;/ 根节点int hgt;/ 树的高度int size;/ 树中不重复节点数量void _insert(AVLNode *& cur, T data);void _mid_travel(AVLNode *cur);/ 层次遍历void _cengci_travel(AVLNode *cur);/ 单旋转（左左，右右） , 左旋不是想左旋转的意思，而是由于左子树的左儿子的高度太大/ 与 treap 的旋转命名相反void _singleRoate(AVLNode *&

6、cur, int dir);/ 双旋转（两次单旋转）void _doubleRoate(AVLNode *& 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);/*私有方法开始*/templatevoid AVLTree

7、:_insert(AVLNode *& cur, T data)if(NULL = cur)cur = new AVLNode(data);else if(data = cur-data)cur-count+;elseint dir = (data cur-data);_insert(cur-sondir, data);lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir);cur-setHeight();/cout set height: show();templatevoid AVLTree:_mid_travel(AVLNode * cu

8、r)if(NULL != cur)/ 先查找做子树_mid_travel(cur-son0);/if(abs(cur-son0-height() - cur-son1-height() = 2)cur-show();_mid_travel(cur-son1);/ 层次遍历，/ 如果节点为空就输出 0 来占位templatevoid AVLTree:_cengci_travel(AVLNode * cur)if(NULL = cur)return;queueAVLNode* q;q.push(cur);AVLNode *top = NULL;queueAVLNode* tmp;while(!q.

9、empty()while(!q.empty()top = q.front();q.pop();if(NULL = top)/ 用 #代表该节点是空， #的后代还是 # cout # ;tmp.push(top);elsecout data.data son0);tmp.push(top-son1);bool flag = false;if(NULL != tmp.front()flag = true;q.push(tmp.front();tmp.pop();cout endl;if(!flag)break;/ 单旋转，即只旋转一次/dir = 0 时 ,左左旋转；否则为右右旋转template

10、void AVLTree:_singleRoate(AVLNode *& cur, int dir) AVLNode *& k2 = cur, * k1 = k2-sondir; /k2 必须是引用 k2-sondir = k1-son!dir;k1-son!dir = k2;k2 = k1;k2-setHeight();k1-setHeight();/ 双旋转，即调两次单旋转/dir = 0 是左右情况；否则为右左情况templatevoid AVLTree:_doubleRoate(AVLNode *& cur, int dir) _singleRoate(cur-sondir, !dir);_singleRoate(cur, dir);/*公有方法（接口）开始*/templatevoid AVLTree:insert(const T & data)_insert(root, data);templatevoid AVLTree:mid_travel()_mid_travel(root);int main()AVLTree* avlt = new AVLTree();const i