均衡二叉樹AVL操作模板。本站提示廣大學習愛好者：（均衡二叉樹AVL操作模板）文章只能為提供參考，不一定能成為您想要的結果。以下是均衡二叉樹AVL操作模板正文
/**
* 目標：完成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;
}
