平衡二叉树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;
}
相关文章
- 这篇文章主要介绍了在C#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了一波二叉树遍历问题的C++解答实例分享,包括节点打印和转换为镜像等问题的解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下...2020-04-25
- 二叉树是数据结构中的树的一种特殊情况,有关二叉树的相关概念,这里不再赘述,如果不了解二叉树相关概念,建议先学习数据结构中的二叉树的知识点...2020-04-25
- 这篇文章主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考下...2017-06-20
- 这篇文章主要介绍了如何在Python中创建二叉树,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-03-30
- 这篇文章主要介绍了C语言 二叉查找树性质详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++基于先序、中序遍历结果重建二叉树的方法,结合实例形式分析了基于C++构建二叉树的相关操作技巧,需要的朋友可以参考下...2020-04-25
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
这篇文章主要介绍了C++基于递归和非递归算法判定两个二叉树结构是否完全相同,若判断二叉树的结构和数据都相同则为完全相同.涉及C++二叉树的创建、遍历、比较等相关操作技巧,需要的朋友可以参考下...2020-04-25- 这篇文章主要为大家详细介绍了C++实现二叉树基本操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言实现二叉树遍历的迭代算法,包括二叉树的中序遍历、先序遍历及后序遍历等,是非常经典的算法,需要的朋友可以参考下...2020-04-25
- 在本篇文章里小编给大家分享了关于c++先序二叉树的构建的相关知识点,需要的朋友们跟着学习下。...2020-04-25
- 这篇文章主要为大家详细介绍了C++二叉树实现词频分析功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了平衡二叉树的实现实例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下...2020-04-25
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
这篇文章主要介绍了C++实现LeetCode(105.由先序和中序遍历建立二叉树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-23- 这篇文章主要介绍了C语言二叉树的非递归遍历,包括了先序遍历、中序遍历与后序遍历,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++非递归建立二叉树的方法,实例分析了二叉树的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25