牛骨文教育服务平台(让学习变的简单)

这里给出了C++代码的实现。关于AVL树的C语言的实现参见《AVL树(Adelson-Velskii-Landis tree)

//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;
}