C語言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(AVL樹)實現(xiàn)方法示例
本文實例講述了C語言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(AVL樹)實現(xiàn)方法。分享給大家供大家參考,具體如下:
AVL樹是每個結(jié)點的左子樹和右子樹的高度最多差1的二叉查找樹。
要維持這個樹,必須在插入和刪除的時候都檢測是否出現(xiàn)破壞樹結(jié)構(gòu)的情況。然后立刻進行調(diào)整。
看了好久,網(wǎng)上各種各種的AVL樹,千奇百怪。
關(guān)鍵是要理解插入的時候旋轉(zhuǎn)的概念。
// // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 2017年 FableGame. All rights reserved. // #ifndef __HelloWorld__AvlTree__ #define __HelloWorld__AvlTree__ #include <iostream> namespace Fable { int max(int a, int b) { return a > b? a:b; } //二叉查找樹,對于Comparable,必須實現(xiàn)了><=的比較 template<typename Comparable> class AvlTree { public: //構(gòu)造函數(shù) AvlTree(){} //復(fù)制構(gòu)造函數(shù) AvlTree(const AvlTree& rhs) { root = clone(rhs.root); } //析構(gòu)函數(shù) ~AvlTree() { makeEmpty(root); } //復(fù)制賦值運算符 const AvlTree& operator=(const AvlTree& rhs) { if (this != &rhs) { makeEmpty(root);//先清除 root = clone(rhs.root);//再復(fù)制 } return *this; } //查找最小的對象 const Comparable& findMin()const { findMin(root); } //查找最大的對象 const Comparable& findMax()const { findMax(root); } //是否包含了某個對象 bool contains(const Comparable& x)const { return contains(x, root); } //樹為空 bool isEmpty()const { return root == nullptr; } //打印整棵樹 void printTree()const { printTree(root); } //清空樹 void makeEmpty() { makeEmpty(root); } //插入某個對象 void insert(const Comparable& x) { insert(x, root); } //移除某個對象 void remove(const Comparable& x) { remove(x, root); } private: struct AvlNode { Comparable element; AvlNode* left; AvlNode* right; int height; AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0) :element(theElement), left(lt), right(rt), height(h){} }; typedef AvlNode* AvlNodePtr; AvlNodePtr root;//根結(jié)點 //順時針旋轉(zhuǎn) void clockwiseRotate(AvlNodePtr& a) { AvlNodePtr b = a->left;//左葉子 a->left = b->right;//a的左葉子變?yōu)閎的右葉子,b本來的子結(jié)點都比a小的。 b->right = a;//b的右結(jié)點指向a,b的高度上升了。 a->height = max(height(a->left), height(a->right)) + 1;//重新計算a的高度 b->height = max(height(b->left), a->height) + 1;//重新計算b的高度 a = b;//a的位置現(xiàn)在是b,當(dāng)前的根結(jié)點 } //逆時針旋轉(zhuǎn) void antiClockWiseRotate(AvlNodePtr& a) { AvlNodePtr b = a->right;//右結(jié)點 a->right = b->left;//a接收b的左結(jié)點 b->left = a;//自己成為b的左結(jié)點 a->height = max(height(a->left), height(a->right)) + 1;//計算高度 b->height = max(b->height, height(a->right)) + 1;//計算高度 a = b;//新的根結(jié)點 } //對左邊結(jié)點的雙旋轉(zhuǎn) void doubleWithLeftChild(AvlNodePtr& k3) { antiClockWiseRotate(k3->left);//逆時針旋轉(zhuǎn)左結(jié)點 clockwiseRotate(k3);//順時針旋轉(zhuǎn)自身 } //對右邊結(jié)點的雙旋轉(zhuǎn) void doubleWithRightChild(AvlNodePtr& k3) { clockwiseRotate(k3->right);//順時針旋轉(zhuǎn)有節(jié)點 antiClockWiseRotate(k3);//逆時針旋轉(zhuǎn)自身 } //插入對象,這里使用了引用 void insert(const Comparable& x, AvlNodePtr& t) { if (!t) { t = new AvlNode(x, nullptr, nullptr); } else if (x < t->element) { insert(x, t->left);//比根結(jié)點小,插入左邊 if (height(t->left) - height(t->right) == 2)//高度差達到2了 { if (x < t->left->element)//插入左邊 { clockwiseRotate(t);//順時針旋轉(zhuǎn) } else { doubleWithLeftChild(t);//雙旋轉(zhuǎn) } } } else if (x > t->element) { insert(x, t->right);//比根結(jié)點大,插入右邊 if (height(t->right) - height(t->left) == 2)//高度差達到2 { if (t->right->element < x)//插入右邊 { antiClockWiseRotate(t);//旋轉(zhuǎn) } else { doubleWithRightChild(t);//雙旋轉(zhuǎn) } } } else { //相同的 } t->height = max(height(t->left), height(t->right)) + 1;//計算結(jié)點的高度 } void removeMin(AvlNodePtr& x, AvlNodePtr& t)const { if (!t) { return;//找不到 } if (t->left) { removeMin(t->left);//使用了遞歸的方式 } else { //找到最小的結(jié)點了 x->element = t->element; AvlNodePtr oldNode = t; t = t->right; delete oldNode;//刪除原來要刪除的結(jié)點 } if (t) { t->height = max(height(t->left), height(t->right)) + 1;//計算結(jié)點的高度 if(height(t->left) - height(t->right) == 2) { //如果左兒子高度大于右兒子高度 if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹高度大于左兒子的右子樹高度 { clockwiseRotate(t); //順時針旋轉(zhuǎn) } else { doubleWithLeftChild(t);//雙旋轉(zhuǎn)左子樹 } } else { if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹大于左子樹 { antiClockWiseRotate(t);//逆時針旋轉(zhuǎn) } else { doubleWithRright(t);//雙旋轉(zhuǎn)右子樹 } } } } //刪除某個對象,這里必須要引用 void remove(const Comparable& x, AvlNodePtr& t)const { if (!t) { return;//樹為空 } else if (x < t->element) { remove(x, t->left);//比根結(jié)點小,去左邊查找 } else if (x > t->element) { remove(x, t->right);//比根結(jié)點大,去右邊查找 } else if (!t->left && !t->right)//找到結(jié)點了,有兩個葉子 { removeMin(t, t->right);//這里選擇的方法是刪除右子樹的最小的結(jié)點 } else { AvlNodePtr oldNode = t; t = (t->left) ? t->left : t->right;//走到這里,t最多只有一個葉子,將t指向這個葉子 delete oldNode;//刪除原來要刪除的結(jié)點 } if (t) { t->height = max(height(t->left), height(t->right)) + 1;//計算結(jié)點的高度 if(height(t->left) - height(t->right) == 2) { //如果左兒子高度大于右兒子高度 if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹高度大于左兒子的右子樹高度 { clockwiseRotate(t); //順時針旋轉(zhuǎn) } else { doubleWithLeftChild(t);//雙旋轉(zhuǎn)左子樹 } } else { if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹大于左子樹 { antiClockWiseRotate(t);//逆時針旋轉(zhuǎn) } else { doubleWithRright(t);//雙旋轉(zhuǎn)右子樹 } } } } //左邊子樹的結(jié)點肯定比當(dāng)前根小的,所以一直往左邊尋找 AvlNodePtr findMin(AvlNodePtr t)const { if (!t) { return nullptr;//找不到 } if (!t->left) { return t; } return findMin(t->left);//使用了遞歸的方式 } //右邊子樹的結(jié)點肯定比當(dāng)前根大,所以一直往右邊找 AvlNodePtr findMax(AvlNodePtr t)const { if (t) { while (t->right)//使用了循環(huán)的方式 { t = t->right; } } return t; } //判斷是否包含某個對象,因為要使用遞歸,所以還有一個public版本的 bool contains(const Comparable& x, AvlNodePtr t)const { if (!t) { return false;//空結(jié)點了 } else if (x < t->element) { //根據(jù)二叉樹的定義,比某個結(jié)點小的對象,肯定只能存在與這個結(jié)點的左邊的子樹 return contains(x, t->left); } else if (x > t->element) { //根據(jù)二叉樹的定義,比某個結(jié)點大的對象,肯定只能存在與這個結(jié)點的右邊的子樹 return contains(x, t->right); } else { //相等,就是找到啦。 return true; } } //清空子樹 void makeEmpty(AvlNodePtr& t) { if (t) { makeEmpty(t->left);//清空左邊 makeEmpty(t->right);//清空右邊 delete t;//釋放自身 } t = nullptr;//置為空 } //打印子樹,這里沒有使用復(fù)雜的排位,純屬打印 void printTree(AvlNodePtr t)const { if (!t) { return; } std::cout << t->element << std::endl;//輸出自身的對象 printTree(t->left);//打印左子樹 printTree(t->right);//打印右子樹 } AvlNodePtr clone(AvlNodePtr t)const { if (!t) { return nullptr; } return new AvlNode(t->element, clone(t->left), clone(t->right)); } int height(AvlNodePtr t)const { return t == nullptr ? -1 : t->height; } }; } #endif
簡單測試一下。
// // AvlTree.cpp // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 2017年 FableGame. All rights reserved. // #include "AvlTree.h" using namespace Fable; int main(int argc, char* argv[]) { AvlTree<int> a; for(int i = 0; i < 100; ++i) { a.insert(i); } return 0; }
這個刪除的方法完全是自己寫的,可能不是很高效。
希望本文所述對大家C語言程序設(shè)計有所幫助。
相關(guān)文章
C語言實現(xiàn)班級檔案管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細介紹了C語言實現(xiàn)班級檔案管理系統(tǒng)課程設(shè)計,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-12-12C++ Primer中&、*符號的多重定義與int *p和int* p的區(qū)別講解
今天小編就為大家分享一篇關(guān)于C++Primer中&、*符號的多重定義與int *p和int* p的區(qū)別講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2019-04-04