AVL树C++实现

系统管理员 2022-08-10 09:50 147阅读 0赞

用C++实现的AVL树代码和解释

#ifndef __AVL_TREE_H__
    #define __AVL_TREE_H__
    
    #include "stdafx.h"

stdafx.h里面有\#include <iostream> \#include <iomanip>

下面是节点

template <class T>
    struct AVLTreeNode {
    	T	key;
    	int height;
    	AVLTreeNode* left;
    	AVLTreeNode* right;
    
    	AVLTreeNode(T value, AVLTreeNode* lt, AVLTreeNode* rt, int h = 0) :
    		key(value), height(h), left(lt), right(rt) {}
    };

template <class T, class Compare = std::less<T> >
    class AVLTree {
    private:
    	AVLTreeNode<T>* root;
    	Compare isLessThan;
    
    public:
    	AVLTree();
    	AVLTree(const AVLTree& rhs);
    	~AVLTree();
    
    	int max(int a, int b) { return a > b ? a : b; }
    	int height()const;			// 获取树的高度
    	void preOrder()const;		// 前序遍历AVL树
    	void inOrder()const;		// 中序遍历AVL树
    	void postOrder()const;		// 后序遍历AVL树
    
    	// (递归实现)查找AVL树中是否存在键值为key的结点
    	bool find(const T& key)const;
    	// (非递归实现)查找AVL树中是否存在键值为key的结点
    	bool iterativeFind(const T& key)const;
    
    	// 查找最小结点，返回最小结点的键值
    	const T& findMin()const;
    	// 查找最大结点，返回最大结点的键值
    	const T& findMax()const;
    
    	// 打印AVL树
    	void print()const;
    
    	// 将结点（key为键值）插入到AVL树中
    	void insert(const T& key);
    	// 将结点（key为键值）从AVL树中删除
    	void remove(const T& key);
    	
    	// 销毁AVL树
    	void destroy();
    	
    	// 重载赋值操作符
    	const AVLTree& operator=(const AVLTree& rhs);
    
    private:
    	int height(AVLTreeNode<T>* node)const;
    
    	void preOrder(AVLTreeNode<T>* node)const;		// 前序遍历AVL树
    	void inOrder(AVLTreeNode<T>* node)const;		// 中序遍历AVL树
    	void postOrder(AVLTreeNode<T>* node)const;		// 后序遍历AVL树
    
    	bool find(AVLTreeNode<T>* node, const T& key)const;
    	bool iterativeFind(AVLTreeNode<T>* node, const T& key)const;
    
    	AVLTreeNode<T>* findMin(AVLTreeNode<T>* node)const;
    	AVLTreeNode<T>* findMax(AVLTreeNode<T>* node)const;
    
    	void print(AVLTreeNode<T>* node, T key, int direction)const;
    	
    	void insert(AVLTreeNode<T>*& node, const T& key);
    	void remove(AVLTreeNode<T>*& node, const T& key);
    
    	void destroy(AVLTreeNode<T>*& node)const;
    
    	void rotateWithLeftChild(AVLTreeNode<T>*& k);		// 左单旋
    	void rotateWithRightChild(AVLTreeNode<T>*& k);		// 右单旋
    
    	void doubleWithLeftChild(AVLTreeNode<T>*& k);		// 左双旋
    	void doubleWithRightChild(AVLTreeNode<T>*& k);		// 右双旋
    
    	AVLTreeNode<T>* clone(const AVLTreeNode<T>* anotherRoot);
    
    };

// constructor
    template <class T, class Compare>
    AVLTree<T, Compare>::AVLTree() {
    	root = NULL;
    }
    
    // copy constructor
    template <class T, class Compare>
    AVLTree<T, Compare>::AVLTree(const AVLTree<T, Compare>& rhs) {
    	root = clone(rhs.root);
    }
    
    // destructor
    template <class T, class Compare>
    AVLTree<T, Compare>::~AVLTree() {
    	destroy();
    }

叶节点的高度为0，NULL的高度为-1

template <class T, class Compare>
    int AVLTree<T, Compare>::height()const {
    	return height(root);
    }
    
    template <class T, class Compare>
    int AVLTree<T, Compare>::height(AVLTreeNode<T>* node)const {
    
    	return (node == NULL) ? -1 : node->height;
    }

![SouthEast][]右单旋

![SouthEast 1][]左单旋

![SouthEast 2][]右双旋

![SouthEast 3][]左双旋

// 对k2的左儿子的左子树进行一次插入
    template <class T, class Compare>
    void AVLTree<T, Compare>::rotateWithLeftChild(AVLTreeNode<T>*& k2) {
    
    	AVLTreeNode<T>* 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), k2->height) + 1;
    	
    	k2 = k1;
    }
    
    // 对k2的右儿子的右子树进行一次插入
    template <class T, class Compare>
    void AVLTree<T, Compare>::rotateWithRightChild(AVLTreeNode<T>*& k2) {
    
    	AVLTreeNode<T>* k1 = k2->right;
    	k2->right = k1->left;
    	k1->left = k2;
    
    	k2->height = max(height(k2->left), height(k2->right)) + 1;
    	k1->height = max(k2->height, height(k1->right)) + 1;
    
    	k2 = k1;
    }
    
    // 对k3的左儿子的右子树进行一次插入
    template <class T, class Compare>
    void AVLTree<T, Compare>::doubleWithLeftChild(AVLTreeNode<T>*& k3) {
    
    	rotateWithRightChild(k3->left);
    	rotateWithLeftChild(k3);
    }
    
    // 对k3的右儿子的左子树进行一次插入
    template <class T, class Compare>
    void AVLTree<T, Compare>::doubleWithRightChild(AVLTreeNode<T>*& k3) {
    
    	rotateWithLeftChild(k3->right);
    	rotateWithRightChild(k3);
    }

insert

// insert
    template <class T, class Compare>
    void AVLTree<T, Compare>::insert(const T& key) {
    	insert(root, key);
    }
    
    /***************************************************************
     * Internal method to insert into a subtree
     * insert通过不断递归直到找到该插入的地方
     * 然后new一个结点，沿着递归的路线从底往上刷新高度
     * 如果在哪个结点发现左儿子和右儿子的高度差为2就单旋转或双旋转
     ***************************************************************/
    template <class T, class Compare>
    void AVLTree<T, Compare>::insert(AVLTreeNode<T>*& node, const T& key) {
    
    	if (node == NULL)
    		node = new AVLTreeNode<T>(key, NULL, NULL);
    	else if (isLessThan(key, node->key)) {
    		insert(node->left, key);
    		// 增加结点后，若AVL树失去平衡，则进行相应的调节
    		// 在node的左子树插入后发现左子树高度-右子树高度=2
    		if (2 == height(node->left) - height(node->right)) {
    			// key小于node左儿子的key
    			if (isLessThan(key, node->left->key))
    				rotateWithLeftChild(node);
    			else
    				doubleWithLeftChild(node);
    		}
    	}
    	else if (isLessThan(node->key, key)) {
    		insert(node->right, key);
    		// 增加结点后，若AVL树失去平衡，则进行相应的调节
    		// 在node的右子树插入后发现右子树高度-左子树高度=2
    		if (2 == height(node->right) - height(node->left)) {
    			// key大于node右儿子的key
    			if (isLessThan(node->right->key, key))
    				rotateWithRightChild(node);
    			else
    				doubleWithRightChild(node);
    		}
    	}
    	else
    		;	// Duplicate; do nothing
    	// 刷新高度
    	node->height = max(height(node->left), height(node->right)) + 1;
    }

remove

![SouthEast 4][]

// remove
    template <class T, class Compare>
    void AVLTree<T, Compare>::remove(const T& key) {
    	remove(root, key);
    }
    
    /**
     * Internal method to remove key from a subtree
     * node 根节点, z 待删除的结点
     * 1.根节点的值小于待删除结点的值
     *     递归
     *     递归返回后若失去平衡则旋转
     * 2.根节点的值大于待删除结点的值
     *     同上
     * 3.根节点的值==待删除结点的值
     *     ⑴若根节点不同时具有左儿子和右儿子
     *         则根节点替换其中一个非空节点（若都空则为NULL）
     *     ⑵若根节点同时具有左儿子和右儿子
     *         则①若左子树较高②若右子树较高（下面细讲）
     */
    template <class T, class Compare>
    void AVLTree<T, Compare>::remove(AVLTreeNode<T>*& node, const T& key) {
    
    	if (NULL == node) return;
    	// 待删除的结点在node的左子树
    	if (isLessThan(key, node->key)) {
    		remove(node->left, key);
    		// 删除结点后，若AVL树失去平衡，则进行相应的调节
    		if (2 == height(node->right) - height(node->left)) {
    			// 下面的if和else条件不能互换，原因见上图
    			AVLTreeNode<T>* rt = node->right;
    			if (isLessThan(height(rt->right), height(rt->left)))
    				doubleWithRightChild(node);
    			else
    				rotateWithRightChild(node);
    		}
    	}
    	// 待删除的结点在node的右子树
    	else if (isLessThan(node->key, key)) {
    		remove(node->right, key);
    		// 删除结点后，若AVL树失去平衡，则进行相应的调节
    		if (2 == height(node->left) - height(node->right)) {
    			// 下面的if和else条件不能互换，原因见上图
    			AVLTreeNode<T>* lt = node->left;
    			if (isLessThan(height(node->left), height(node->right)))
    				doubleWithLeftChild(node);
    			else
    				rotateWithLeftChild(node);
    		}
    	}
    	// node是要删除的结点
    	else {
    		// node同时有左儿子和右儿子
    		if (NULL != node->left && NULL != node->right) {
    
    			if (isLessThan(height(node->right), height(node->left))) {
    				// node的左子树比右子树高
    				// 1.找出node左子树中的最大节点
    				// 2.将该最大节点的值赋给node
    				// 3.删除该最大节点
    				// 这类似于用"node的左子树中最大节点"做"node"的替身
    				// 采用这种方式的好处是：删除"node的左子树中最大节点"之后，AVL树仍是平衡的
    				AVLTreeNode<T>* leftMax = findMax(node->left);
    				node->key = leftMax->key;
    				remove(node->left, leftMax->key);
    			}
    			else {
    				// 如果node的左子树不比右子树高(相等或者右子树比左子树高1)
    				// 1.找出node右子树中的最小节点
    				// 2.将该最小节点的值赋给node
    				// 3.删除该最小节点
    				// 这类似于用"node的右子树中最小节点"做"node"的替身
    				// 采用这种方式的好处是：删除"node的右子树中最小节点"之后，AVL树仍是平衡的
    				AVLTreeNode<T>* rightMin = findMin(node->right);
    				node->key = rightMin->key;
    				remove(node->right, rightMin->key);
    			}
    		}
    		else {
    			AVLTreeNode<T>* tmp = node;
    			node = (NULL != node->left) ? node->left : node->right;
    			delete tmp;
    		}
    	}
    }

// 前序遍历AVL树 (DLR)
    template <class T, class Compare>
    void AVLTree<T, Compare>::preOrder()const {
    	preOrder(root);
    }
    
    // Internal method: 前序遍历AVL树
    template <class T, class Compare>
    void AVLTree<T, Compare>::preOrder(AVLTreeNode<T>* node)const {
    
    	if (NULL != node) {
    		std::cout << node->key << " ";
    		preOrder(node->left);
    		preOrder(node->right);
    	}
    }
    
    // 中序遍历AVL树 (LDR)
    template <class T, class Compare>
    void AVLTree<T, Compare>::inOrder()const {
    	inOrder(root);
    }
    
    // Internal method: 中序遍历AVL树
    template <class T, class Compare>
    void AVLTree<T, Compare>::inOrder(AVLTreeNode<T>* node)const {
    
    	if (NULL != node) {
    		inOrder(node->left);
    		std::cout << node->key << " ";
    		inOrder(node->right);
    	}
    }
    
    // 后序遍历AVL树 (LRD)
    template <class T, class Compare>
    void AVLTree<T, Compare>::postOrder()const {
    	postOrder(root);
    }
    
    // Internal method: 后序遍历AVL树
    template <class T, class Compare>
    void AVLTree<T, Compare>::postOrder(AVLTreeNode<T>* node)const {
    
    	if (NULL != node) {
    		postOrder(node->left);
    		postOrder(node->right);
    		std::cout << node->key << " ";
    	}
    }

</pre><pre name="code" class="cpp">// findMin
    template <class T, class Compare>
    const T& AVLTree<T, Compare>::findMin()const {
    
    	AVLTreeNode<T>* tmp = findMin(root);
    
    	if (NULL == tmp) 
    		throw out_of_range("AVLTree is empty.");
    	else
    		return tmp->key;
    }
    // Internal method: findMin
    template <class T, class Compare>
    AVLTreeNode<T>* AVLTree<T, Compare>::findMin(AVLTreeNode<T>* node)const {
    
    	if (NULL == node)
    		return NULL;
    	// 没有必要用递归
    	while (NULL != node->left) {
    		node = node->left;
    	}
    	return node;
    } 
    
    // findMax
    template <class T, class Compare>
    const T& AVLTree<T, Compare>::findMax()const {
    
    	AVLTreeNode<T>* tmp = findMax(root);
    
    	if (NULL == tmp)
    		throw out_of_range("AVLTree is empty.");
    	else
    		return tmp->key;
    }
    
    // Internal method: findMax
    template <class T, class Compare>
    AVLTreeNode<T>* AVLTree<T, Compare>::findMax(AVLTreeNode<T>* node)const {
    
    	if (NULL == node) return NULL;
    
    	while (NULL != node->right) {
    		node = node->right;
    	}
    	return node;
    }
    
    // find
    template <class T, class Compare>
    bool AVLTree<T, Compare>::find(const T& key)const {
    	return find(root, key);
    }
    
    // Internal method: find
    template <class T, class Compare>
    bool AVLTree<T, Compare>::find(AVLTreeNode<T>* node, const T& key)const {
    
    	if (NULL == node) return false;
    
    	if (isLessThan(node->key, key)) {
    		find(node->right, key);
    	}
    	else if (isLessThan(key, node->key)) {
    		find(node->left, key);
    	}
    	else
    		return true;
    }
    
    // iterativeFind
    template <class T, class Compare>
    bool AVLTree<T, Compare>::iterativeFind(const T& key)const {
    	iterativeFind(root, key);
    }
    
    // Internal method: iterativeFind
    template <class T, class Compare>
    bool AVLTree<T, Compare>::iterativeFind(AVLTreeNode<T>* node, const T& key)const {
    	
    	while ((NULL != node) && (key != node->key)) {
    		if (isLessThan(key, node->key))
    			node = node->left;
    		else
    			node = node->right;
    	}
    	if (NULL == node->key) return false;
    	else return true;
    }

// destroy
    template <class T, class Compare>
    void AVLTree<T, Compare>::destroy() {
    	destroy(root);
    }
    
    // Internal method: destroy
    template <class T, class Compare>
    void AVLTree<T, Compare>::destroy(AVLTreeNode<T>*& node)const {
    
    	if (NULL == node) return;
    
    	destroy(node->left);
    	destroy(node->right);
    
    	delete node;
    	node = NULL;
    }
    
    // print
    template <class T, class Compare>
    void AVLTree<T, Compare>::print()const {
    	if (NULL != root)
    		print(root, root->key, 0);
    }
    
    // Internal method: print
    template <class T, class Compare>
    void AVLTree<T, Compare>::print(AVLTreeNode<T>* node, T key, int direction)const {
    
    	if (NULL != node) {
    
    		if (direction == 0)	{	// node是根节点
    			std::cout << std::setw(2) << node->key << " is root" << std::endl;
    		}
    		else {
    			std::cout << std::setw(2) << node->key << " is " << std::setw(2) << key
    				<< "'s " << std::setw(12)
    				<< (direction == 1 ? "right child" : "left child") << std::endl;
    		}
    		print(node->left, node->key, -1);
    		print(node->right, node->key, 1);
    	}
    }
    
    // Internal method: clone
    template <class T, class Compare>
    AVLTreeNode<T>* AVLTree<T, Compare>::clone(const AVLTreeNode<T>* anotherRoot) {
    
    	if (NULL == anotherRoot) return NULL;
    
    	else return new AVLTreeNode<T>(anotherRoot->key, clone(anotherRoot->left), 
    		clone(anotherRoot->right), anotherRoot->height);
    
    }
    
    // operator=
    template <class T, class Compare>
    const AVLTree<T, Compare>& AVLTree<T, Compare>::operator=(const AVLTree<T, Compare>& rhs) {
    
    	if (this != &rhs) {
    		this->destroy();
    		this->root = clone(rhs.root);
    	}
    	return *this;
    }
    
    
    #endif

\-main.cpp 测试

![SouthEast 5][]

#include "stdafx.h"
    #include "AVLTree.h"
    using namespace std;
    
    void order(const AVLTree<int>& iAVLTree);
    
    int main()
    {
    	AVLTree<int> iAVLTree;
    
    	int ia[] = { 3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9 };
    
    	for (int i = 0; i < 16; ++i) {
    		iAVLTree.insert(ia[i]);		// insert
    	}
    
    	iAVLTree.remove(8);		// remove
    
    	order(iAVLTree);		// 各种遍历
    	iAVLTree.print();		// 打印
    
    	if (!iAVLTree.find(8)) cout << "cannot find 8." << endl;	// find
    	if (iAVLTree.iterativeFind(9)) cout << "find 9." << endl;	// iterativeFind
    
    	cout << "max: " << iAVLTree.findMax() << "  "		// max
    		<< "min: " << iAVLTree.findMin() << endl;		// min
    	cout << "height: " << iAVLTree.height() << endl;	// height
    
    	AVLTree<int> iAVLTree2(iAVLTree);	// copy constructor
    	cout << "iAVLTree's height: " << iAVLTree2.height() << endl;
    
    	AVLTree<int> iAVLTree3;
    	iAVLTree3 = iAVLTree2;				// operator=
    	cout << "iAVLTree's max: " << iAVLTree3.findMax()
    		<< " and min: " << iAVLTree3.findMin() << endl;
    
    	system("pause");
    	return 0;
    }
    
    // 各种遍历
    void order(const AVLTree<int>& iAVLTree) {
    	cout << "前序遍历：";
    	iAVLTree.preOrder();
    	cout << endl;
    	cout << "中序遍历：";
    	iAVLTree.inOrder();
    	cout << endl;
    	cout << "后序遍历：";
    	iAVLTree.postOrder();
    	cout << endl;
    }

![SouthEast 6][]

参考：http://www.cnblogs.com/skywang12345/p/3577360.html\#a2

[SouthEast]: /images/20220731/067e3ffcc28b40d19a232fa6d4c90382.png
[SouthEast 1]: /images/20220731/d5fb226e49e0424bb9ac5e75ae0eb1c2.png
[SouthEast 2]: /images/20220731/53dfe242945340c0b3173951833eb587.png
[SouthEast 3]: /images/20220731/4480fee89194472bb74417c88a45efbe.png
[SouthEast 4]: /images/20220731/765806a67de84e2aae9659533492391a.png
[SouthEast 5]: /images/20220731/28cc3edddd7d46d79c6936bdcf66a989.png
[SouthEast 6]: /images/20220731/309314fa313c4369bf73e7ef3c911d36.png