C++實現(xiàn)AVL樹的完整代碼
更新時間：2021年06月02日 10:28:41 作者：QS小其
AVL樹是高度平衡的而二叉樹。它的特點是：AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1。 今天通過本文給大家分享C++實現(xiàn)AVL樹的完整代碼，感興趣的朋友一起看看吧
AVL樹的介紹
AVL樹是一種自平衡的二叉搜索樹，它通過單旋轉(zhuǎn)（single rotate）和雙旋轉(zhuǎn)(double rotate)的方式實現(xiàn)了根節(jié)點的左子樹與右子樹的高度差不超過1,。這有效的降低了二叉搜索樹的時間復雜度，為O（log n）。那么，下面小編將詳細介紹C++實現(xiàn)AVL樹的代碼。最后一步提供可靠的代碼實現(xiàn)
這里先粘貼代碼
給大家的忠告，一定要及時去實現(xiàn)，不然之后再實現(xiàn)要花更多的時間
/*
*平衡二叉樹應該有些功能
*插入 刪除 查找
*前序遍歷 中序遍歷 后序遍歷 層次遍歷
*統(tǒng)計結(jié)點數(shù)目
*/
//代碼已經(jīng)調(diào)好，寫了很久才寫出來
#ifndef _AVLTREE_
#define _AVLTREE_
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define MAXFACTOR = 2;
template<class Key , class E>
class AVLNode
{
private:
Key key;
E value;
AVLNode<Key,E>* left;
AVLNode<Key,E>* right;
AVLNode<Key,E>* parent;
public:
AVLNode():left(nullptr),right(nullptr),parent(nullptr){}
AVLNode(Key _key,E _value , AVLNode<Key,E>* _parent = nullptr,AVLNode<Key,E>*_left = nullptr, AVLNode<Key,E>*_right = nullptr):
key(_key),value(_value),left(_left),right(_right),parent(_parent){}
bool isLeaf(){return left==nullptr && right == nullptr ;}
//元素設置
Key getKey() const { return key;}
void setKey(Key set) {key = set;}
E getValue() const { return value;}
void setValue(E set) {value = set;}
AVLNode<Key,E>* getLeft() { return left; }
void setLeft (AVLNode< Key,E >* set){ left = set;}
AVLNode<Key,E>* getRight() { return right;}
void setRight (AVLNode<Key,E>* set) {right = set ;}
AVLNode<Key,E>* getParent() {return parent;}
void setParent(AVLNode<Key,E>* set) { parent = set;}
};
template<class Key , class E>
class AVLTree
{
private:
AVLNode<Key,E>* root;
void clear(AVLNode<Key,E>* &r)
{
if(r==nullptr)return;
if(r->getLeft())clear(r->getLeft());
if(r->getRight())clear(r->getRight);
delete r;
}
void Init()
{
root = new AVLNode<Key,E>();
root=nullptr;
}
void preOrder(AVLNode<Key,E>* r,void(*visit) (AVLNode<Key,E> * node))
{
if(r==nullptr)return;
(*visit) (r);
preOrder(r->getLeft() , visit);
preOrder(r->getRight(), visit);
}
void inOrder(AVLNode<Key,E>* r , void(*visit)(AVLNode<Key,E>* node) )
{
if(r==nullptr)return;
inOrder(r->getLeft() , visit);
(*visit)(r);
inOrder(r->getRight(),visit);
}
void postOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
{
if(r==nullptr)return;
postOrder(r->getLeft(),visit);
postOrder(r->getRight(),visit);
(*visit)(r);
}
void levelOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
{
queue< AVLNode<Key,E>* > q;
if(r==nullptr)return;
q.push(r);
while( ! q.empty() )
{
AVLNode<Key,E>* tmp = q.front();
q.pop();
(*visit)(tmp);
if(tmp->getLeft() ) q.push(tmp->getLeft() );
if(tmp->getRight()) q.push(tmp->getRight());
}
}
AVLNode<Key,E>* find(AVLNode<Key,E>* r,Key k)
{
if(r==nullptr)return nullptr;
if(k == r->getKey() ) return r;
else if( k < r->getKey())
{
find(r->getLeft(),k);
}
else {
find(r->getRight(),k);
}
}
//Find the smallest element in the avl tree
AVLNode<Key,E>* getMin(AVLNode<Key,E>* r)
{
if(r->getLeft() == nullptr) return r;
else{
getMin(r->getLeft());
}
}
//Remove the smallest element
AVLNode<Key,E>* deleteMin(AVLNode<Key,E>* rt)
{
if(rt->getLeft() == nullptr) return rt->getRight();
else{
rt->setLeft(deleteMin(rt->getLeft()));
return rt;
}
}
AVLNode<Key,E>* leftRotate(AVLNode<Key,E>* node)
{
if( node == nullptr) return nullptr;
AVLNode<Key,E>* newHead = node->getRight();
node->setRight( newHead -> getLeft() );
newHead -> setLeft( node );
return newHead;
}
AVLNode<Key,E>* rightRotate(AVLNode<Key,E>* node)
{
if(node == nullptr)return nullptr;
AVLNode<Key,E>* newHead = node->getLeft();
node->setLeft( newHead->getRight() );
newHead ->setRight(node);
return newHead;
}
int getHeight(AVLNode<Key,E>*node)
{
if(node == nullptr)return 0;
if(node->isLeaf())return 1;
else return ( getHeight( node->getLeft() ) > getHeight( node->getRight() ) ?
getHeight( node->getLeft() ) : getHeight( node->getRight() ) ) + 1;
}
int getBalanceFactor(AVLNode<Key,E>* node)
{
return getHeight(node->getLeft()) - getHeight(node->getRight() );
}
AVLNode<Key,E>* balance(AVLNode<Key,E>* node)
{
if(!node) return nullptr;
else if ( getBalanceFactor( node ) == 2)
{
if(getBalanceFactor( node ->getLeft() ) == 1)
{
node = rightRotate(node);
}
else
{
node->setLeft(leftRotate( node->getLeft() ) );
node = rightRotate(node);
}
}
else if(getBalanceFactor( node ) == -2)
{
if(getBalanceFactor( node->getRight()) == -1)
{
node = leftRotate(node);
}
else
{
node->setRight( rightRotate( node->getRight() ) );
node = leftRotate(node);
}
}
return node;
}
AVLNode<Key,E>* insert( AVLNode<Key,E>* root ,const pair<Key,E>& it)
{
if(root == nullptr)
{
return new AVLNode<Key,E>(it.first , it.second,NULL,NULL,NULL);
}
else if (it.first < root->getKey() )
{
root ->setLeft( insert(root->getLeft() , it) ) ;
}
else{
root ->setRight( insert(root->getRight() , it) );
}
root = balance(root);
return root;
}
AVLNode<Key,E>* remove(AVLNode<Key,E>* node , const Key k)
{
if(node == nullptr) return nullptr;
if(node->getKey() > k)
{
node->setLeft( remove(node->getLeft() , k) );
node = balance(node);
}
else if(node->getKey() < k)
{
node->setRight( remove(node->getRight(), k) );
node = balance(node);
}
else if(node->getKey() == k)
{
if(! node->isLeaf() )
{
AVLNode<Key,E>* tmp = getMin(node->getRight() );
node->setKey( tmp->getKey() );
node->setValue( tmp->getValue() );
node->setRight( deleteMin(node->getRight() ) );
delete tmp;
}
else {
AVLNode<Key,E>* tmp = node;
node = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight() ;
delete tmp;
}
}
return node;
}
public:
~AVLTree(){clear(root);}
AVLTree(){/*Init();*/ root = nullptr; }
//四種遍歷方式
void preOrder( void (*visit)(AVLNode<Key,E>* r))
{
preOrder(root,visit);
}
void inOrder(void (*visit)(AVLNode<Key,E>* r))
{
inOrder(root,visit);
}
void postOrder(void (*visit)(AVLNode<Key,E>* r))
{
postOrder(root,visit);
}
void levelOrder( void(*visit)(AVLNode<Key,E>*r) )
{
levelOrder(root,visit);
}
//插入
void insert(const pair<Key,E> &it)
{
root = insert(root,it);
}
//刪除
void remove(const Key& k)
{
remove(root,k);
}
bool find(const Key&k)
{
return find(root,k);
}
};
#endif
//AVLtest.cpp
#include"NewAvl.h"
#include<iostream>
using namespace std;
template<typename Key,typename E>
void traverse(AVLNode<Key,E>* root)
{
cout<<root->getKey()<<" "<<root->getValue()<<" ";
cout<<endl;
}
int main()
{
AVLTree<int,int>* tree = new AVLTree<int ,int>;
for(int i = 0 ; i < 5 ; i ++)
{
tree->insert(make_pair(i,i));
}
tree->remove(1);
cout<<"PreOrder: "<<endl;
tree->preOrder(traverse);
cout<<endl;
cout<<"LevelOrder: "<<endl;
tree->levelOrder(traverse);
cout<<endl;
cout<<"InOrder: "<<endl;
tree->inOrder(traverse);
cout<<endl;
cout<<"PostOrder: "<<endl;
tree->postOrder(traverse);
cout<<endl;
cout<<tree->find(2)<<endl;
tree->insert(make_pair(9,9));
tree->levelOrder(traverse);
}
運行結(jié)果
以上就是C++實現(xiàn)AVL樹的完整代碼的詳細內(nèi)容，更多關(guān)于C++ AVL樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++實現(xiàn)LeetCode(228.總結(jié)區(qū)間)
這篇文章主要介紹了C++實現(xiàn)LeetCode(228.總結(jié)區(qū)間),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
內(nèi)存管理是C++最令人切齒痛恨的問題，也是C++最有爭議的問題，C++高手從中獲得了更好的性能，更大的自由，今天給大家分享C/C++內(nèi)存管理的實例代碼，需要的朋友參考下吧2021-06-06
大家好，本篇文章主要講的是C語言實現(xiàn)第一次防死版掃雷游戲，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了C語言中如何實現(xiàn)單鏈表刪除指定結(jié)點，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
今天小編就為大家分享一篇關(guān)于C++函數(shù)與指針的文章，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2021-10-10
JetBrains?CLion永久激活超詳細教程(最新激活方法)
JetBrains?Clion?是一款專為?C/C++?開發(fā)所設計的跨平臺?IDE，本文適用?JetBrains?CLion?v2019.3/3.1/3.2/3.3?永久激活，附破解補丁和激活碼，可以永久激活?Windows、MAC、Linux?下的?CLion，下面給大家分享JetBrains?CLion永久激活超詳細教程，感興趣的朋友一起看看吧2023-01-01
本篇文章是對C++讀寫Excel的實現(xiàn)方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C語言結(jié)構(gòu)體指針案例解析,本文通過例子來解釋說明了C語言的結(jié)構(gòu)體概念和如何用指針去操作結(jié)構(gòu)體,文章標明了詳細的代碼,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語言枚舉的使用以及使用，閱讀下面內(nèi)容我們將掌握枚舉的相關(guān)概念、掌握枚舉的幾種用法、掌握枚舉在實際產(chǎn)品中的用法,需要的朋友可以參考一下2022-03-03
? 互斥量是一種同步原語,用于保護多個線程同時訪問共享數(shù)據(jù),互斥量提供獨占的、非遞歸的所有權(quán)語義,本文將和大家一起深入探究C/C++中互斥量(鎖)的實現(xiàn)原理,感興趣的小伙伴跟著小編一起來看看吧2024-06-06