a亚洲精品_精品国产91乱码一区二区三区_亚洲精品在线免费观看视频_欧美日韩亚洲国产综合_久久久久久久久久久成人_在线区

首頁 > 編程 > C > 正文

平衡二叉樹AVL操作模板

2020-01-26 15:35:46
字體:
供稿:網(wǎng)友

復(fù)制代碼 代碼如下:

/**
* 目的:實(shí)現(xiàn)AVL
* 利用數(shù)組對左右兒子簡化代碼,但是對腦力難度反而增大不少,只適合acm模板
* 其實(shí)avl在acm中基本不用,基本被treap取代
* avl一般只要求理解思路,不要求寫出代碼,因?yàn)檎嫘暮軣?BR>*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <time.h>
#include <queue>
using namespace std;

int COUNT; //統(tǒng)計(jì)樹中不重復(fù)節(jié)點(diǎn)的個(gè)數(shù)
int HEIGHT; //統(tǒng)計(jì)數(shù)的高度

//數(shù)據(jù)節(jié)點(diǎn)
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的節(jié)點(diǎn)
template<class T>
class AVLNode{
private:
 int hgt; //節(jié)點(diǎn)的高度
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是節(jié)點(diǎn)中的數(shù)據(jù)類型
template<class T>
class AVLTree{
private:
 AVLNode<T> * root;  //根節(jié)點(diǎn)
 int hgt;   //樹的高度
 int size;   //樹中不重復(fù)節(jié)點(diǎn)數(shù)量
 void _insert(AVLNode<T> *& cur, T data);
 void _mid_travel(AVLNode<T> *cur);
 //層次遍歷
 void _cengci_travel(AVLNode<T> *cur);
 //單旋轉(zhuǎn)(左左,右右), 左旋不是想左旋轉(zhuǎn)的意思, 而是由于左子樹的左兒子的高度太大
 //與treap的旋轉(zhuǎn)命名相反
 void _singleRoate(AVLNode<T> *& cur, int dir);
 //雙旋轉(zhuǎn)(兩次單旋轉(zhuǎn))
 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]);
 }
}
//層次遍歷,
//如果節(jié)點(diǎn)為空就輸出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){
    //用#代表該節(jié)點(diǎn)是空,#的后代還是#
    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;
 }
}

//單旋轉(zhuǎn),即只旋轉(zhuǎn)一次
//dir = 0時(shí),左左旋轉(zhuǎn);否則為右右旋轉(zhuǎn)
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();
}
//雙旋轉(zhuǎn),即調(diào)兩次單旋轉(zhuǎn)
//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 << "**************中序遍歷結(jié)束**********" << endl;

 cout << "*************層次遍歷開始***************" << endl;
 avlt->cengci_travel();
 cout << "**************層次遍歷結(jié)束**********" << endl;
 cout << "樹的高度是: " << avlt->height() << endl;
 return 0;
}

發(fā)表評論 共有條評論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表

圖片精選

主站蜘蛛池模板: 亚洲一区二区av | 在线婷婷| 欧美精品在线一区二区 | 久草热8精品视频在线观看 高清av一区 | 色综合天天综合网国产成人网 | 久草视频网址 | 一区二区三区日韩精品 | 亚洲成人综合在线 | 色婷婷中文字幕 | 国产婷婷精品av在线 | 热久久久久 | 国产在线一区二区三区 | 青青草免费在线 | 国产丝袜一区二区三区免费视频 | 免费的黄色av网站 | 国产女人和拘做受视频 | 婷婷色5月 | 午夜一区二区三区在线观看 | 狠狠爱www人成狠狠爱综合网 | 亚洲性爰 | 另类天堂 | 午夜免费看片 | 美女久久久久 | 日韩欧美视频一区 | 九九九九精品 | 国严精品久久久久久亚洲影视 | segui88久久综合9999 | 欧美日韩一区二区三区在线观看 | 天堂av一区二区 | av一区二区三区 | 免费一区二区三区视频在线 | 成人免费视频视频在线观看 免费 | 欧洲一区二区在线观看 | 国产伦理一区二区 | 午夜视频一区二区 | 嫩草研究院在线观看入口 | 欧美一区二区国产 | 最新版天堂资源中文在线 | 亚洲欧洲一区二区 | 亚洲成人一区二区在线观看 | 欧美视频二区 |