本例子分為3個文件。

類聲明頭文件 hAVL.h #ifndef AVLTREE_H_INCLUDED #define AVLTREE_H_INCLUDED//AVL樹數據結構定義 typedef int ElementType;//AVL數節點包含數據類型//樹節點 typedef struct AVLNode{ElementType element;//節點包含的數據元素AVLNode *left;//節點左子樹AVLNode *right;//節點右子樹int height;//節點所在的高度 }*AVLTree;//AVL tree類封裝 class CAVLTree{ private://供內部調用的函數int getHeight(AVLTree);//求得樹的高度void setHeight(AVLTree, int);//設置節點的高度值//單旋轉：向右旋轉 AVLTree SingleRightRotate(AVLTree);//單旋轉：向左旋轉 AVLTree SingleLeftRotate(AVLTree);//雙旋轉：左右 AVLTree DoubleRightRotate(AVLTree);//雙旋轉：右左 AVLTree DoubleLeftRotate(AVLTree);public://默認構造函數 CAVLTree();//析構函數~CAVLTree();//創建AVL樹void createAVLTree(ElementType *data, int n);//插入節點 AVLTree insertNode(AVLTree T, ElementType val);//刪除樹中元素值等于某值的節點AVLTree deleteNode(AVLTree T, const ElementType val);//搜尋元素值等于某值的節點 AVLTree searchNode(AVLTree, ElementType);//前序遍歷輸出樹void preOrder(AVLTree T);//得到樹中的元素值最大的節點 AVLTree getMaxNode(AVLTree);//得到樹中的元素值最小的那個節點 AVLTree getMinNode(AVLTree);void deleteTree(AVLTree t);AVLTree T; };#endif // AVLTREE_H_INCLUDED //右右外側插入導致的不平衡，采用單旋轉-左旋轉進行修正 //參數解釋：類實現文件AVLTr.cpp #include "stdafx.h" #include "hAVL.h"#include <iostream> #include <cmath> #include <math.h> #include <cassert>using namespace std;int fmax(int i, int j) {return i>j?i:j; };CAVLTree::CAVLTree() {T = NULL; }CAVLTree::~CAVLTree() {deleteTree(T); }//依據各元素的數據值，創建AVL樹 void CAVLTree::createAVLTree(ElementType *data, int n) {if (T){cout << "The AVL Tree has been created" << endl;return;}if (!n)//元素序列為空 {T = NULL;return;}for (int i = 0; i < n; ++i){T = insertNode(T, *(data + i));}return; }AVLTree CAVLTree::insertNode(AVLTree T, ElementType val) {AVLNode *pNewNode = new AVLNode;pNewNode->element = val;pNewNode->left = NULL;pNewNode->right = NULL;pNewNode->height = 1;//新節點一定被插入在空節點的位置if (NULL == T){T = pNewNode;return T;}//需要插入節點的樹非空//插入的元素已經存在于樹中，不符合要求if (val == T->element){cout << "元素中有重復，構建AVL樹失敗！" << endl;return T;}//要插入的值小于根節點的值，將其插入左子樹中if (val < T->element){//將其插入根節點的左子樹中T->left = insertNode(T->left, val);//判斷平衡條件是否仍然滿足if (getHeight(T->left) - getHeight(T->right) > 1){//分兩種情況進行旋轉操作//插入點位于T的左子結點的左子樹if (val < T->left->element)//實施單旋轉-右旋轉T = SingleRightRotate(T);else//插入點位于T的左子結點的右子樹，實施雙右旋轉T = DoubleRightRotate(T);}}//要插入的值大于根節點的值，將其插入右子樹中if (val > T->element){T->right = insertNode(T->right, val);//判斷平衡條件是否仍然滿足if (getHeight(T->right) - getHeight(T->left) > 1){//節點插入到T的右子節點的右子樹中if (val > T->right->element)//實施單旋轉-左旋轉T = SingleLeftRotate(T);else//節點插入到T的右子節點的左子樹上//實施雙旋轉-左旋轉T = DoubleLeftRotate(T);}}//更新節點的height值setHeight(T, fmax(getHeight(T->left), getHeight(T->right)) + 1);return T; }AVLTree CAVLTree::deleteNode(AVLTree T, const ElementType val) {if (!T){cout << "The tree is NULL, delete failed" << endl;return T;}AVLTree searchedNode = searchNode(T, val);//沒有找到相應的節點，刪除失敗if (!searchedNode){cout << "Cann't find the node to delete " << val << endl;return T;}//找到了需要刪除的節點//需要刪除的節點就是當前子樹的根節點if (val == T->element){//左右子樹都非空if (T->left && T->right){//在高度更大的那個子樹上進行刪除操作if (getHeight(T->left) > getHeight(T->right)){//左子樹高度大，刪除左子樹中元素值最大的那個節點，同時將其值賦值給根節點T->element = getMaxNode(T->left)->element;T->left = deleteNode(T->left, T->element);}else{//刪除右子樹中元素值最小的那個節點，同時將其值賦值給根節點T->element = getMinNode(T->right)->element;T->right = deleteNode(T->right, T->element);}}else{//左右子樹中有一個不為空，那個直接用需要被刪除的節點的子節點替換之即可AVLTree oldNode = T;T = (T->left ? T->left : T->right);delete oldNode;//釋放節點所占的空間oldNode = NULL;}}else if (val < T->element)//要刪除的節點在左子樹中 {//在左子樹中進行遞歸刪除T->left = deleteNode(T->left, val);//判斷是否仍然滿足平衡條件if (getHeight(T->right) - getHeight(T->left) > 1){if (T->right->left > T->right->right){//左雙旋轉T = DoubleLeftRotate(T);}else//進行左單旋轉T = SingleLeftRotate(T);}else//滿足平衡條件，需要更新高度信息T->height = fmax(getHeight(T->left), getHeight(T->right)) + 1;}else//需要刪除的節點在右子樹中 {T->right = deleteNode(T->right, val);//判斷是否滿足平衡條件if (getHeight(T->left) - getHeight(T->right) > 1){if (getHeight(T->left->right) > getHeight(T->left->left))//右雙旋轉T = DoubleRightRotate(T);else//右單旋轉T = SingleRightRotate(T);}else//只需調整高度即可T->height = fmax(getHeight(T->left), getHeight(T->right)) + 1;}return T; }AVLTree CAVLTree::searchNode(AVLTree T, ElementType val) {if (!T){return NULL;}//搜索到if (val == T->element){return T;}else if (val < T->element){//在左子樹中搜索return searchNode(T->left, val);}else{//在右子樹中搜索return searchNode(T->right, val);} }void CAVLTree::preOrder(AVLTree T) {if (!T)cout << "NULL ";else{cout << T->element << " ";preOrder(T->left);preOrder(T->right);} }AVLTree CAVLTree::getMaxNode(AVLTree T) {if (!T)//樹為空 {return NULL;}AVLTree tempNode = T;//向右搜尋直至右子節點為NULLwhile (tempNode->right){tempNode = tempNode->right;}return tempNode; }AVLTree CAVLTree::getMinNode(AVLTree T) {if (!T)//樹為空 {return NULL;}AVLTree tempNode = T;//向左搜尋直至左子結點為NULLwhile (tempNode->left){tempNode = tempNode->left;}return tempNode; }int CAVLTree::getHeight(AVLTree T) {return (T == NULL) ? 0 : (T->height); }void CAVLTree::setHeight(AVLTree T, int height) {T->height = height; }//左左外側插入導致的不平衡，采用單旋轉-右旋轉進行修正 //參數解釋： //T：指向因某種操作失去平衡的最小子樹根節點 AVLTree CAVLTree::SingleRightRotate(AVLTree T) {AVLTree xPNode = T;AVLTree yPNode = T->left;xPNode->left = yPNode->right;//更改原根節點的左子樹yPNode->right = xPNode;//更改原根節點左孩子的右子樹//更新進行了旋轉操作的節點的高度xPNode->height = fmax(getHeight(xPNode->left), getHeight(xPNode->right)) + 1;yPNode->height = fmax(getHeight(yPNode->left), getHeight(yPNode->right)) + 1;//原根節點的左孩子節點成為新的根節點return yPNode;//T：指向因某種操作失去平衡的最小子樹根節點 AVLTree CAVLTree::SingleLeftRotate(AVLTree T) {AVLTree xPNode = T;AVLTree yPNode = T->right;xPNode->right = yPNode->left;//更改原根節點的右孩子yPNode->left = xPNode;//提升原根節點的右孩子節點為新的根節點//更新執行了旋轉操作的節點的高度信息xPNode->height = fmax(getHeight(xPNode->left), getHeight(xPNode->right)) + 1;yPNode->height = fmax(getHeight(yPNode->left), getHeight(yPNode->right)) + 1;//返回新的根節點return yPNode; }//插入點位于T的左子結點的右子樹 AVLTree CAVLTree::DoubleRightRotate(AVLTree T) {//雙旋轉可以通過兩次單旋轉實現//第一次單旋轉assert(T->left != NULL);//對其左子樹進行一次單旋轉-左旋轉T->left = SingleLeftRotate(T->left);//第二次單旋轉//對新產生的樹進行一次單旋轉-右旋轉return SingleRightRotate(T); }//插入點位于T的右子節點的左子樹 AVLTree CAVLTree::DoubleLeftRotate(AVLTree T) {//雙旋轉可以通過兩次單旋轉實現//第一次單旋轉assert(T->right != NULL);//對其右子樹進行一次單旋轉-右旋轉T->right = SingleRightRotate(T->right);//第二次單旋轉//對新產生的樹進行一次單旋轉-左旋轉return SingleLeftRotate(T); }void CAVLTree::deleteTree(AVLTree t) {if (NULL == t)return;deleteTree(t->left);deleteTree(t->right);delete t;t = NULL; } 主函數文件 main.cpp // AVLTree.cpp : 定義控制臺應用程序的入口點。 // #include "stdafx.h"//平衡二叉樹搜索樹（AVL tree-Adelson-Velskii-Landis tree）編程實現 #include "hAVL.h" #include <iostream> using namespace std;int main() {// 通過給定序列創建平衡二叉樹const int NumElements = 8;cout << "AVL樹各項操作編程實現：" << endl;int a[NumElements] = { 25,2,64,45,12,34,9,18};CAVLTree *CAVLTreeObj1 = new CAVLTree();CAVLTreeObj1->createAVLTree(a, NumElements);cout << "AVL Tree先序遍歷結果：" << endl;CAVLTreeObj1->preOrder(CAVLTreeObj1->T);cout << endl;// 插入一個新的數據int insertedVal1 = 15;CAVLTreeObj1->T = CAVLTreeObj1->insertNode(CAVLTreeObj1->T, insertedVal1);cout << "向AVL樹中插入元素 " << insertedVal1 << "之后的先序遍歷結果：" << endl;CAVLTreeObj1->preOrder(CAVLTreeObj1->T);cout << endl << endl;// 在插入一個新的數據（由重復數據情況下）int insertedVal2 = 16;CAVLTreeObj1->T = CAVLTreeObj1->insertNode(CAVLTreeObj1->T, insertedVal2);cout << "向AVL樹中插入元素 " << insertedVal2 << "之后的先序遍歷結果：" << endl;CAVLTreeObj1->preOrder(CAVLTreeObj1->T);cout << endl << endl;// 尋找最小的元素int minVal = CAVLTreeObj1->getMinNode(CAVLTreeObj1->T)->element;cout << "樹中最小的元素是：" << minVal << endl;cout << endl;// 尋找最大的元素int maxVal = CAVLTreeObj1->getMaxNode(CAVLTreeObj1->T)->element;cout << "樹中最大的元素是：" << maxVal << endl;cout << endl;// 刪除1個元素const int deletedVal1 = 11;CAVLTreeObj1->T = CAVLTreeObj1->deleteNode(CAVLTreeObj1->T, deletedVal1);cout << "刪除元素值為 " << deletedVal1 << "的節點之后的樹先序遍歷結果：" << endl;CAVLTreeObj1->preOrder(CAVLTreeObj1->T); cout << endl << endl;// 刪除第2個元素const int deletedVal2 = 20;CAVLTreeObj1->T = CAVLTreeObj1->deleteNode(CAVLTreeObj1->T, deletedVal2);cout << "刪除元素值為 " << deletedVal2 << "的節點之后的樹先序遍歷結果：" << endl;CAVLTreeObj1->preOrder(CAVLTreeObj1->T);cout << endl << endl;// 刪除第3個元素const int deletedVal3 = 18;CAVLTreeObj1->T = CAVLTreeObj1->deleteNode(CAVLTreeObj1->T, deletedVal3);cout << "刪除元素值為 " << deletedVal3 << "的節點之后的樹先序遍歷結果：" << endl;CAVLTreeObj1->preOrder(CAVLTreeObj1->T);cout << endl << endl;const int searchedVal1 = 12;AVLTree searchedPNode = CAVLTreeObj1->searchNode(CAVLTreeObj1->T, searchedVal1);if (!searchedPNode)cout << "cannot find such node whose elemen equals " << searchedVal1 << endl;elsecout << "search success element " << searchedVal1 << endl;const int searchedVal2 = 13;searchedPNode = CAVLTreeObj1->searchNode(CAVLTreeObj1->T, searchedVal2);if (!searchedPNode)cout << "cannot find such node whose elemen equals " << searchedVal2 << endl;elsecout << "search success element " << searchedVal2 << endl;cout << endl << endl;getchar();return 0; }

?

轉載于:https://www.cnblogs.com/gd-luojialin/p/8509131.html

總結

以上是生活随笔為你收集整理的16-1平衡树源代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。