avl树的C++实现
最后更新于：2022-04-01 16:17:27
这里给出了C++代码的实现。关于AVL树的C语言的实现参见《[AVL树（Adelson-Velskii-Landis tree）](http://blog.csdn.net/u013074465/article/details/44672567)》
~~~
//3avl_tree_c++.h
#ifndef AVL_TREE_cplusplus_H
#define AVL_TREE_cplusplus_H
#include <iostream>
using namespace std;
template <typename Comparable>
class AvlTree
{
public:
AvlTree():root(NULL) {}
AvlTree(const AvlTree &rhs): root(NULL) {
*this = rhs;
}
~AvlTree() {
makeEmpty();
}
const Comparable &findMin() const {
if (isEmpty())
cout << "树为空" << endl;
return findMin(root)->element;
}
const Comparable &findMax() const {
if (isEmpty())
cout << "树为空" << endl;
return findMax(root)->element;
}
bool contains(const Comparable &x) const {
return contains(x, root);
}
bool isEmpty() const {
return root == NULL;
}
void printTree() const {
if (isEmpty())
cout << "Empty tree." << endl;
else {
cout << "先序：";
printTreePreOrder(root);
cout << endl << "中序：";
printTreeInOrder(root);
cout << endl << "后序：";
printTreePostOrder(root);
}
cout << endl;
}
void makeEmpty() {
makeEmpty(root);
}
void insert(const Comparable &x) {
insert(x, root);
}
void remove(const Comparable &x) {
remove(x, root);
}
const AvlTree &operator=(const AvlTree &rhs) {
if (this != &rhs) {
makeEmpty();
root = clone(rhs.root);
}
return this;
}
private:
struct AvlNode
{
Comparable element;
AvlNode *left;
AvlNode *right;
int height;
AvlNode(const Comparable &theElement, AvlNode *l, AvlNode *r, int h = 0):
element(theElement), left(l), right(r), height(h) {}
};
AvlNode *root;
void insert(const Comparable &x, AvlNode* &t) {
if (t == NULL)
t = new AvlNode(x, NULL, NULL);
else if (x < t->element) {
insert(x, t->left);
if (height(t->left) - height(t->right) == 2)
if (x < t->left->element)
rotateWithLeftChild(t);
else
doubleWithLeftChild(t);
}
else if (x > t->element) {
insert(x, t->right);
if (height(t->right) - height(t->left) == 2)
if (t->right->element < x)
rotateWithRightChild(t);
else
doubleWithRightChild(t);
}
else
; //要往树中插入已经存在的元素，什么也不做
t->height = max(height(t->left), height(t->right)) + 1;
}
void remove(const Comparable &x, AvlNode* &t) {
if (t == NULL)
return;
if (x < t->element) {
remove(x, t->left);
if (height(t->right) - height(t->left) == 2) {
if (height(t->right->left) > height(t->right->right))
doubleWithRightChild(t);
else
rotateWithRightChild(t);
}
}
else if (x > t->element) {
if (height(t->left) - height(t->right) == 2) {
if (height(t->left->right) > height(t->left->left))
doubleWithLeftChild(t);
else
rotateWithLeftChild(t);
}
}
else if (t->left && t->right) { //找到要删除的位置，t有两个孩子
t->element = findMin(t->right)->element;
remove(t->element, t->right);
t->height = max(height(t->left), height(t->right)) + 1;
}
else {
AvlNode *oldNode = t;
t = (t->left == NULL) ? t->right : t->left;
delete oldNode;
}
if (t != NULL)
t->height = max(height(t->left), height(t->right)) + 1;
}
AvlNode *findMin(AvlNode *t) const {
if (t == NULL)
return NULL;
if (t->left == NULL)
return t;
return findMin(t->left);
}
AvlNode *findMax(AvlNode *t) const {
//注释部分为递归
//if (t == NULL)
// return NULL;
//if (t->right == NULL)
// return t;
//return findMax(t->right);
//非递归形式
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
bool contains(const Comparable &x, AvlNode *t) const {
if (t == NULL)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (x > t->element)
return contains(x, t->right);
else
return true;
}
/*
//非迭代操作
bool contains(const Comparable &x, AvlNode *t) {
while (t != NULL) {
if (x < t->element)
t = t->left;
else if (x > t->element)
t = t->right;
else
return true;
}
return false;
}
*/
void makeEmpty(AvlNode* &t) {
if (t != NULL) {
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
void printTreePreOrder(AvlNode *t) const {
if (t != NULL) {
cout << t->element << " ";
printTreePreOrder(t->left);
printTreePreOrder(t->right);
}
}
void printTreeInOrder(AvlNode * t) const {
if (t != NULL) {
printTreeInOrder(t->left);
cout << t->element << " ";
printTreeInOrder(t->right);
}
}
void printTreePostOrder(AvlNode * t) const {
if (t != NULL) {
printTreePostOrder(t->left);
printTreePostOrder(t->right);
cout << t->element << " ";
}
}
AvlNode *clone(AvlNode *t) const {
if (t == NULL)
return NULL;
return new AvlNode(t->element, clone(t->left), clone(t->right));
}
int height(AvlNode *t) const {
return t == NULL ? -1 : t->height;
}
int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
//单旋转，左-左
void rotateWithLeftChild(AvlNode * & k2) {
AvlNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2 = k1;
}
//单旋转，右-右
void rotateWithRightChild(AvlNode * & k1) {
AvlNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1 = k2;
}
//双旋转，左-右
void doubleWithLeftChild(AvlNode * & k3) {
rotateWithRightChild(k3->left);
rotateWithLeftChild(k3);
}
//双旋转，右-左
void doubleWithRightChild(AvlNode * & k3) {
rotateWithLeftChild(k3->right);
rotateWithRightChild(k3);
}
};
#endif
~~~
测试代码：
~~~
#include "3avl_tree_c++.h"
int main() {
AvlTree<int> tree;
int i = 0;
while (i != 9) {
tree.insert(i++);
}
tree.printTree();
cout << endl << "删除11但11不存在：" << endl;
tree.remove(11);
tree.printTree();
cout << endl << "删除 5和8：" << endl;
tree.remove(5);
tree.remove(8);
tree.printTree();
return 0;
}
~~~
