包括3个文件:AvlNode.h AvlTree.h和main.cpp
1.节点类的定义AvlNode.h
#ifndef AVLNODE_H
#define AVLNODE_H
#include <iostream>
using namespace std;
template <class T> class AvlTree; //声明AvlTree类
template <class T>
class AvlNode{
public:
friend class AvlTree<T>;//友元类
//构造函数
AvlNode():left(NULL),right(NULL),balance(0){};
AvlNode(const T& e,AvlNode<T> *lt = NULL,AvlNode<T> *rt = NULL):data(e),left(lt),right(rt),balance(0){};
int getBalance() const{return balance;}
AvlNode<T>* getLeft() const{return left;}
AvlNode<T>* getRight() const{return right;}
T getData() const{return data;}
private:
T data; //节点的值
AvlNode *left; //左孩子
AvlNode *right; //有孩子
int balance; //平衡因子,右子树的高度减去左子树的高度
};
#endif //AVLNODE_H
2.AvlTree.h
#ifndef AVLTREE_H
#define AVLTREE_H
#include <iostream>
#include <queue>
#include <iomanip>
#include "AvlNode.h"
using namespace std;
template <class T>
class AvlTree{
public:
AvlTree():root(NULL){}
AvlNode<T>* getRoot() const{return root;}
bool Insert(T x){ bool taller = false; return Insert(root,x,taller ); }
bool Delete(T x){ bool shorter = false; return Delete(root,x,shorter); }
void PrintTree() const{PrintTree(root,0);}
void PrintTreeLevel() const{PrintTreeLevel(root);}
void PrintTreePre() const{PrintTreePre(root);}
void PrintTreePost() const{PrintTreePost(root);}
void PrintTreeIn() const{PrintTreeIn(root);}
private:
AvlNode<T> *root;
bool Insert(AvlNode<T> *& sRoot,T x,bool &taller);
bool Delete(AvlNode<T> *& sRoot,T x,bool &shorter);
void RotateLeft(AvlNode<T> * &sRoot);
void RotateRight(AvlNode<T> * &sRoot);
void RightBalanceAfterInsert(AvlNode<T> * &sRoot,bool &taller);
void LeftBalanceAfterInsert(AvlNode<T> * &sRoot,bool &taller);
void RightBalanceAfterDelete(AvlNode<T> * &sRoot,bool &shorter);
void LeftBalanceAfterDelete(AvlNode<T> * &sRoot,bool &shorter);
void PrintTree(AvlNode<T> *t,int layer) const;
void PrintTreeLevel(AvlNode<T> *t) const;
void PrintTreePre(AvlNode<T> *t) const;
void PrintTreePost(AvlNode<T> *t) const;
void PrintTreeIn(AvlNode<T> *t) const;
};
template <typename T>
//左旋函数
void AvlTree<T>::RotateLeft(AvlNode<T> * &sRoot){
if( (sRoot == NULL) || (sRoot->right == NULL) ) return;
AvlNode<T> *temp = new AvlNode<T>(sRoot->data);
if(temp == NULL ) return;
temp->left = sRoot->left;
sRoot->left = temp;
temp->right = sRoot->right->left;
AvlNode<T> *toDelete = sRoot->right;
sRoot->data = toDelete->data;
sRoot->right = toDelete->right;
delete toDelete;
}
template <typename T>
//右旋函数
void AvlTree<T>::RotateRight(AvlNode<T> * &sRoot){
if( (sRoot == NULL) || (sRoot->left == NULL) ) return;
AvlNode<T> *temp = new AvlNode<T>(sRoot->data);
if(temp == NULL ) return;
temp->right = sRoot->right;
sRoot->right = temp;
temp->left = sRoot->left->right;
AvlNode<T> *toDelete = sRoot->left;
sRoot->data = toDelete->data;
sRoot->left = toDelete->left;
delete toDelete;
}
template <typename T>
void AvlTree<T>::RightBalanceAfterInsert(AvlNode<T> *&sRoot,bool &taller){
//如果插入节点后,sRoot的右高度增加引起不平衡，则调用此函数，使树重新平衡
if( (sRoot == NULL) || (sRoot->right == NULL) ) return;
AvlNode<T> *rightsub = sRoot->right,*leftsub;
switch(rightsub->balance){
case 1:
sRoot->balance = rightsub->balance = 0;
RotateLeft(sRoot);
taller = false; break;
case 0:
cout<<"树已经平衡化."<<endl; break;
case -1:
leftsub = rightsub->left;
switch(leftsub->balance){
case 1:
sRoot->balance = -1; rightsub->balance = 0; break;
case 0:
sRoot->balance = rightsub->balance = 0; break;
case -1:
sRoot->balance = 0; rightsub->balance = 1; break;
}
leftsub->balance = 0;
RotateRight(rightsub);
RotateLeft(sRoot);
taller = false; break;
}
}
template <typename T>
void AvlTree<T>::LeftBalanceAfterInsert(AvlNode<T> *&sRoot,bool &taller){
//如果插入节点后,sRoot的左高度增加,引起不平衡，则调用此函数，使树重新平衡
AvlNode<T> *leftsub = sRoot->left,*rightsub;
switch(leftsub->balance){
case -1:
sRoot->balance = leftsub->balance = 0;
RotateRight(sRoot);
taller = false; break;
case 0:
cout<<"树已经平衡化."<<endl; break;
case 1:
rightsub = leftsub->right;
switch(rightsub->balance){
case -1:
sRoot->balance = 1; leftsub->balance = 0; break;
case 0:
sRoot->balance = leftsub->balance = 0; break;
case 1:
sRoot->balance = 0; leftsub->balance = -1; break;
}
rightsub->balance = 0;
RotateLeft(leftsub);
RotateRight(sRoot);
taller = false; break;
}
}
template <typename T>
void AvlTree<T>::RightBalanceAfterDelete(AvlNode<T> * &sRoot,bool &shorter){
//如果删除节点后，sRoot的左高度减少，引起不平衡，则调用此函数，使树重新平衡
AvlNode<T> *rightsub = sRoot->right,*leftsub;
switch(rightsub->balance){
case 1: sRoot->balance = sRoot->balance = 0; RotateLeft(sRoot); break;
case 0: sRoot->balance = 0; rightsub->balance = -1; RotateLeft(sRoot); break;
case -1:
leftsub = rightsub->left;
switch(leftsub->balance){
case -1: sRoot->balance = 0; rightsub->balance = 1; break;
case 0: sRoot->balance = rightsub->balance = 0; break;
case 1: sRoot->balance = -1; rightsub->balance = 0; break;
}
leftsub->balance = 0;
RotateRight(rightsub);
RotateLeft(sRoot);
shorter = false; break;
}
}
template <typename T>
void AvlTree<T>::LeftBalanceAfterDelete(AvlNode<T> * &sRoot,bool &shorter){
//如果删除节点后，sRoot的右高度减少，引起不平衡，则调用此函数，使树重新平衡
AvlNode<T> *leftsub = sRoot->left,*rightsub;
switch(leftsub->balance){
case 1: sRoot->balance = sRoot->balance = 0; RotateRight(sRoot); break;
case 0: sRoot->balance = 0; leftsub->balance = -1; RotateRight(sRoot); break;
case -1:
rightsub = leftsub->right;
switch(rightsub->balance){
case -1: sRoot->balance = 0; leftsub->balance = 1; break;
case 0: sRoot->balance = leftsub->balance = 0; break;
case 1: sRoot->balance = -1; leftsub->balance = 0; break;
}
rightsub->balance = 0;
RotateLeft(leftsub);
RotateRight(sRoot);
shorter = false; break;
}
}
template <typename T>
bool AvlTree<T>::Insert(AvlNode<T> *& sRoot,T x,bool &taller){
//递归函数,从sRoot这棵树寻找合适的位置,插入值为x的节点
bool success;
if ( sRoot == NULL ) {//函数的出口,从叶节点插入
sRoot = new AvlNode<T>(x);
success = sRoot != NULL ? true : false;
if ( success ) taller = true;
}
else if ( x < sRoot->data ) {//如果x的值小于sRoot的值
//Insert的递归调用,从sRoot的左子树寻找合适的位置插入
success = Insert ( sRoot->left, x, taller );
if ( taller ){//如果插入后使得sRoot的左高度增加
switch ( sRoot->balance ) {
case -1 : LeftBalanceAfterInsert( sRoot, taller ); break;
case 0 : sRoot->balance = -1; break;
case 1 : sRoot->balance = 0; taller = false; break;
}
}
}
else if ( x > sRoot->data ) {//如果x的值大于sRoot的值
//Insert的递归调用,从sRoot的右子树寻找合适的位置插入
success = Insert ( sRoot->right, x, taller );
if ( taller ){//如果插入后使得sRoot的右高度增加
switch ( sRoot->balance ) {
case -1 : sRoot->balance = 0; taller = false; break;
case 0 : sRoot->balance = 1; break;
case 1 : RightBalanceAfterInsert( sRoot, taller ); break;
}
}
}
return success;
}
template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *& sRoot,T x,bool &shorter){
//递归函数,从sRoot这棵子树寻找值为x的节点，并删除之.
bool success = false;
if(sRoot == NULL) return false; //空树，操作失败
if(x == sRoot->data) {//如果sRoot就是要删除的节点
if(sRoot->left != NULL && sRoot->right != NULL) {//如果sRoot有个子女
//寻找 sRoot的中序遍历的前驱节点,用r表示
AvlNode<T> *r = sRoot->left;
while(r->right != NULL) {
r = r->right;
}
//交换sRoot和r的值
T temp = sRoot->data;
sRoot->data = r->data;
r->data = temp;
//递归函数调用,从sRoot的左子树寻找值为x的节点，并删除之.
success = Delete(sRoot->left, x, shorter);
if(shorter) {//如果删除后引起sRoot的左高度减少
switch(sRoot->balance) {
case -1: sRoot->balance = 0; break;
case 0: sRoot->balance = 1; shorter = 0; break;
case 1: RightBalanceAfterDelete(sRoot, shorter);break;
}
}
}
else {//sRoot最多只有一个子女,这是递归的出口
AvlNode<T> *p = sRoot;
sRoot = sRoot->left != NULL ? sRoot->left : sRoot->right;//令sRoot指向它的子女
delete p;//释放原来sRoot所占的内存空间
success = true;
shorter = true;
}
}
else if(x < sRoot->data) {
//递归函数调用,从sRoot的左子树寻找值为x的节点，并删除之.
success = Delete(sRoot->left, x, shorter);
if(shorter) {//如果删除后引起sRoot的左高度减少
switch(sRoot->balance) {
case -1: sRoot->balance = 0; break;
case 0: sRoot->balance = 1; shorter = 0; break;
case 1: RightBalanceAfterDelete(sRoot, shorter); break;
}
}
}
else if(x > sRoot->data) {
//递归函数调用,从sRoot的右子树寻找值为x的节点，并删除之.
success = Delete(sRoot->right, x, shorter);
if(shorter) {//如果删除后引起sRoot的右高度减少
switch(sRoot->balance) {
case -1: LeftBalanceAfterDelete(sRoot, shorter); break;
case 0: sRoot->balance = -1; shorter = 0; break;
case 1: sRoot->balance = 0; break;
}
}
}
return success;
}
template <typename T>
void AvlTree<T>::PrintTree(AvlNode<T> *t,int layer) const{
if(t == NULL ) return;
if(t->right) PrintTree(t->right,layer+1);
for(int i =0;i<layer;i++) cout<<" ";
cout<<t->data<<endl;
if(t->left) PrintTree(t->left,layer+1);
}
template <typename T>
void AvlTree<T>::PrintTreeLevel(AvlNode<T> *t) const{
if(t == NULL) return;
queue<AvlNode<T>*> NodeQueue;
AvlNode<T> *node;
NodeQueue.push(t);
while(!NodeQueue.empty()){
node = NodeQueue.front();
NodeQueue.pop();
cout<<node->data<<",";
if(node->left != NULL) NodeQueue.push(node->left);
if(node->right != NULL) NodeQueue.push(node->right);
}
}
template <typename T>
void AvlTree<T>::PrintTreePre(AvlNode<T> *t) const{
if(t){
cout<<t->data<<",";
PrintTreePre(t->left);
PrintTreePre(t->right);
}
}
template <typename T>
void AvlTree<T>::PrintTreePost(AvlNode<T> *t) const{
if(t){
PrintTreePost(t->left);
PrintTreePost(t->right);
cout<<t->data<<",";
}
}
template <typename T>
void AvlTree<T>::PrintTreeIn(AvlNode<T> *t) const{
if(t){
PrintTreeIn(t->left);
cout<<t->data<<",";
PrintTreeIn(t->right);
}
}
#endif //AVLsRoot_H
3.main.cpp
#include <iostream>
#include <stdlib.h>
#include "AvlTree.h"
//#include "BTree.h"
//#include "BSTree.h"
using namespace std;
int main(){
AvlTree<int> l;
for(int i = 1 ; i <= 15 ; i++){
l.Insert(i);
}
l.PrintTree();
while(true){
int toDelete;
cout<<"请输入要删除节点的值:"<<endl;
cin>>toDelete;
l.Delete(toDelete);
cout<<"删除后的树为:"<<endl;
l.PrintTree();
}
return 0;
system("PAUSE");
}
分享到：
相关推荐
AVL树是一种自平衡二叉查找树，由G....总的来说，理解AVL树的工作原理并能用C++实现它，对于掌握数据结构和算法有着重要的意义。通过实践，你可以深入理解树的平衡策略以及如何利用C++的模板类进行泛型编程。
学习AVL树的算法实现，使用c++在vc6.0中进行相应的算法实现，对正在学习算法的孩子有帮助
通过理解这些核心概念，你可以阅读源码并了解AVL树的C++实现细节。同时，由于测试平台为Linux，源码可能使用了标准库或特定于Linux的函数，如动态内存管理（`new`/`delete`）和文件操作等。确保在合适的环境中编译和...
AVL树是一种自平衡二叉查找树（Binary Search Tree，简称BST），由Georgy Adelson-Velsky和Emanuel Landis在1962年提出，因此...通过深入研究提供的文本文件，我们可以更深入地了解AVL树的平衡调整策略和C++实现细节。
总的来说，这个C++实现的AVL树利用了模板类的灵活性和`shared_ptr`的自动内存管理，能够高效且安全地处理二叉查找树的各种操作。理解AVL树的原理和实现对于提升数据结构与算法能力，尤其是处理动态数据集时的性能...
AVL树是一种自平衡二叉查找树（Binary Search Tree，...以上是C++实现AVL树的基础知识点，具体实现过程会涉及更多细节，如旋转的具体代码实现、错误处理等。在实际编码时，还需要注意C++语法和面向对象设计原则的运用。
总的来说，AVL树的C++实现涉及对二叉树操作的理解、自平衡算法的掌握以及可能的控制台或图形化绘制技术。理解和实现AVL树可以帮助我们深入理解数据结构，提高算法设计和问题解决的能力。在实际应用中，AVL树常被用于...
AVL树是一种自平衡二叉查找树（BST），由G....以上就是关于AVL树的基本概念、插入和删除操作以及C++实现的详细说明。通过理解和掌握这些知识，你可以创建一个高效的AVL树数据结构，并在实际项目中利用其优势。
在C++中实现AVL树，我们需要关注以下几个关键点： 1. **数据结构定义**：首先，我们需要定义一个表示节点的结构体或类，包括键值、高度、左右子节点的指针。例如： ```cpp struct TreeNode { int key; int ...
4. C++实现： - 定义AVL树节点结构体，包含值、高度、左子节点和右子节点指针。 - 实现AVL树的插入函数，包括插入逻辑和平衡调整。 - 实现AVL树的删除函数，处理各种删除情况并进行平衡调整。 - 实现打印函数，...
本话题主要探讨了C++实现的二叉树、二叉搜索树以及AVL树，这些都是高级数据结构，对于优化算法和提高程序效率至关重要。 二叉树是一种特殊的树结构，每个节点最多只有两个子节点，通常分为左子节点和右子节点。在...
在`avl_tree`这个文件中，很可能包含了AVL树的C++、Java或Python等编程语言的实现，包括节点定义、插入、删除和以括号表示法输出等功能。通过阅读和理解这些代码，你可以深入学习AVL树的工作原理和实际应用。
AVL树的平衡性比红黑树更强，因此在查找效率上通常优于红黑树，但插入和删除操作可能需要更多的旋转，导致更复杂的实现。红黑树的平衡要求相对较宽松，插入和删除操作的代价较低，且在实践中表现良好，是许多语言...
在C++中实现AVL树，首先需要定义一个AVL树节点结构体，包括存储元素的关键值、指向左子树和右子树的指针，以及一个用于存储该节点平衡因子的额外字段。平衡因子是节点的左子树高度减去其右子树高度的差值。当节点的...
在C++中实现AVL树，通常采用面向对象的方法，即定义一个表示树节点的类，并提供相应的成员函数来处理插入、删除和平衡操作。下面将详细解释这些概念： 1. **AVL树节点类**： - 定义一个Node类，包含三个成员：key...
总的来说，这个压缩包提供了C++实现的两种高效自平衡二叉查找树，具有良好的性能和易用性，适合于需要高效存储和操作有序数据的场合。通过学习和使用这些模板，开发者可以提升他们的算法能力，并在实际项目中实现更...