AVL.h文件代碼

#pragma once #include<iostream> #include<stack>#include <assert.h> using namespace std; using namespace std; template<class T> struct AVLNode{T data;AVLNode<T>*left, *right;int bf;AVLNode() :left(NULL), right(NULL), bf(0) {}AVLNode(T d, AVLNode<T>*l=NULL,AVLNode<T>*r=NULL):data(d),left(l),right(r),bf(0){} }; template<class T> class AVLTree { public:AVLTree():root(NULL){}~AVLTree() {};AVLTree(T Ref):Refvalue(Ref),root(NULL){}bool insert(AVLNode<T>*&ptr, T&e1);bool Remove(AVLNode<T>*&ptr, T x);void RotateL(AVLNode<T>*&ptr);void RotateR(AVLNode<T>*&ptr);void PrintBinTree(AVLNode<T>*&t, int level);void RotateLR(AVLNode<T>*&ptr);void RotateRL(AVLNode<T>*&ptr);AVLNode<T>* search(const T x, AVLNode<T>*ptr);friend istream& operator>>(istream&, AVLTree<T>& Tree);friend ostream& operator<<(ostream&, AVLTree<T>&Tree);void Delete(AVLNode<T>*ptr);void output(AVLNode<T>*ptr, ostream&out);AVLNode<T>*root;T Refvalue; private:}; template<class T> void AVLTree<T>::RotateL(AVLNode<T>*&ptr) {AVLNode<T>*subL = ptr;ptr = subL->right;subL->right = ptr->left;ptr->left = subL;ptr->bf = subL->bf = 0; } template<class T> void AVLTree<T>::RotateR(AVLNode<T>*&ptr) {AVLNode<T>*subR = ptr;ptr = subR->left;subR->left = ptr->right;ptr->right = subR;ptr->bf = subR->bf = 0; } template<class T> void AVLTree<T>::RotateLR(AVLNode<T>*&ptr) {AVLNode<T>*subR = ptr, *subL = subR->left;ptr = subL->right;subL->right = ptr->left;ptr->left = subL;if (ptr->bf <= 0)subL->bf = 0;else subL->bf = -1;subR->left = ptr->right;ptr->right = subR;if (ptr->bf == -1)subR->bf = 1;else subR->bf = 0;ptr->bf = 0; } template<class T> void AVLTree<T>::RotateRL(AVLNode<T>*&ptr) {AVLNode<T>*subL = ptr, *subR = subL->right;ptr = subR->left;subR->left = ptr->right;ptr->right = subR;if (ptr->bf >= 0)subR->bf = 0;else subR->bf = 1;subL->right = ptr->left;ptr->left = subL;if (ptr->bf == 1)subL->bf = -1;else subL->bf = 0;ptr->bf = 0; } template<class T> bool AVLTree<T>::insert(AVLNode<T>*&ptr, T&e1) {AVLNode<T>*pr = NULL, *p = ptr, *q; int d;stack<AVLNode<T>*>st;while (p!=NULL){if (e1 == p->data) {cout << "存在，無法插入\n"; return false;}pr = p; st.push(pr);if (e1 < p->data)p = p->left;else p = p->right;}p = new AVLNode<T>(e1);if (p == NULL) { cout << "內(nèi)存不足" << endl; exit(1); }if (pr == NULL) { ptr = p; return true; }//空樹，根結(jié)點插入if (e1 < pr->data)pr->left = p;else pr->right = p;while (st.empty()==false){pr = st.top();st.pop();if (p == pr->left)pr->bf--;else pr->bf++;if (pr->bf == 0)break;//case 1,平衡退出if (abs(pr->bf) == 1) {//case 2p = pr;//回溯}else {//case 3 |bf|==2d = (pr->bf < 0) ? -1 : 1;if (p->bf == d) {if (d == -1)RotateR(pr);else RotateL(pr);}else {if (d == -1)RotateLR(pr);else RotateRL(pr);}break;}}if (st.empty() == true)ptr = pr;else {q = st.top();if (q->data > pr->data)q->left = pr;else q->right = pr;}return true; } //template<class T> istream& operator >>(istream& in, AVLTree<int>& Tree) {int item;in >> item;while (item!=Tree.Refvalue){Tree.insert(Tree.root,item);in >> item;}return in; }//template<class T> ostream& operator<<( ostream&out, AVLTree<int>&Tree) {out << "中序遍歷輸出各個結(jié)點數(shù)值:" << endl;Tree.output(Tree.root,out);out << endl;return out;} template<class T> void AVLTree<T>::output(AVLNode<T>*ptr, ostream&out) {if (ptr != NULL) {output(ptr->left, out);cout << ptr->data << " ";output(ptr->right, out);} } template<class T> AVLNode<T>* AVLTree<T>::search(const T x, AVLNode<T>*ptr) {if (ptr == NULL)return NULL;else if (x < ptr->data)return search(x, ptr->left);else if (x > ptr->data)return search(x, ptr->right);else return ptr; }template<class T> void AVLTree<T>::Delete(AVLNode<T>*ptr) {if (ptr != NULL){Delete(ptr->left);Delete(ptr->right);delete ptr;}}template <class T> void AVLTree<T>::PrintBinTree(AVLNode<T>*&t, int level) {if (t == NULL)return;PrintBinTree(t->right, level + 1);for (int i = 0; i < 4 * (level - 1); i++)cout << " ";cout << t->data << endl;PrintBinTree(t->left, level + 1); }template<class T> bool AVLTree<T>::Remove(AVLNode<T>*&t, T val) {assert(t != nullptr);AVLNode<T> *tmp = t;AVLNode<T> *pre_tmp = nullptr;AVLNode<T> *ppre_tmp = nullptr;AVLNode<T> *it_tmp = nullptr;stack<AVLNode<T>*> st;int sign, lable; //符號標記int flag = 0; //子樹標記，下文具體解釋while (tmp != nullptr) {if (tmp->data == val) //找到跳出循環(huán)break;pre_tmp = tmp;st.push(pre_tmp);if (tmp->data > val)tmp = tmp->left;elsetmp = tmp->right;}if (tmp == nullptr) //未找到，返回return false;else if (tmp->left!= nullptr && tmp->right != nullptr) {pre_tmp = tmp; //將有兩個孩子的節(jié)點轉(zhuǎn)化為只有一個孩子的節(jié)點，方法是尋找它中序遍歷的直接前驅(qū)或后繼st.push(pre_tmp);it_tmp = tmp->left;while (it_tmp->right!= nullptr) {pre_tmp = it_tmp;st.push(pre_tmp);it_tmp = it_tmp->right;}tmp->data = it_tmp->data; //覆蓋要刪除的節(jié)點tmp = it_tmp; //tmp指向要刪除的節(jié)點，函數(shù)結(jié)束前會delete tmp}if (tmp->left!= nullptr) { //這樣的判斷方式會導(dǎo)致刪除一個節(jié)點下兩個沒有孩子節(jié)點的節(jié)點時，由于左孩子均為空，直接跳入elseit_tmp = tmp->left;}else {it_tmp = tmp->right;}if (pre_tmp == nullptr)t = it_tmp;else {if (pre_tmp->left== tmp) { //上面直接跳入else，但我們在此處加上flag，用來識別它到底是pre_tmp的左孩子還是右孩子。flag = 0;pre_tmp->left= it_tmp;}else {flag = 1;pre_tmp->right = it_tmp;}while (!st.empty()) {pre_tmp = st.top();st.pop();if (pre_tmp->left == it_tmp && flag == 0)//此處flag=0，防止pre_tmp的左孩子為空，右孩子同樣為空，直接進入elsepre_tmp->bf++;elsepre_tmp->bf--;if (!st.empty()){ppre_tmp = st.top();if (ppre_tmp->left == pre_tmp){sign = -1; //sign用來識別是祖父節(jié)點的左孩子還是右孩子，下文鏈接會用上flag = 0;}else {sign = 1;flag = 1;}}elsesign = 0; //棧空，它的祖先節(jié)點不存在，pre_tmp即為根節(jié)點，但是這里也要寫上，否則sign的值會遺留下來if (pre_tmp->bf == -1 || pre_tmp->bf == 1)break; //已經(jīng)平衡，直接跳出if (pre_tmp->bf != 0) { //m_bf為+2/-2if (pre_tmp->bf < 0) {lable = -1; //lable表示父節(jié)點符號，下面會用來區(qū)分同號異號it_tmp = pre_tmp->left;}else {lable = 1;it_tmp = pre_tmp->right;}if (it_tmp->bf == 0) { //pre_tmp的較高子樹的頭節(jié)點m_bf為0if (lable == -1) {RotateR(pre_tmp);pre_tmp->bf = 1;pre_tmp->right->bf = -1;}else {RotateL(pre_tmp);pre_tmp->bf = -1;pre_tmp->left->bf = 1;}break; //直接跳出，并沒有鏈接，需要下文寫上鏈接}if (it_tmp->bf == lable) { //同號 lable == 1 ? RotateL(pre_tmp) : RotateLR(pre_tmp);}else { //異號lable == -1 ? RotateLR(pre_tmp): RotateRL(pre_tmp);}//sign == -1 ? ppre_tmp->left_child = pre_tmp //不能寫成這樣，因為sign值可能為0，會直接進入后者// : ppre_tmp->right_child = pre_tmp; //!!!!! sign maybe 0 ! not only1 or -1 !!! warning!if (sign == -1)ppre_tmp->left = pre_tmp;else if (sign == 1) //else if正確方式ppre_tmp->right = pre_tmp;}it_tmp = pre_tmp; //回溯}if (st.empty()) //棧為空，根節(jié)點t = pre_tmp;else { //這一段else參考書上沒有，書是錯的，如果不寫此處，290break直接跳出while循環(huán)，會導(dǎo)致鏈接不上，數(shù)據(jù)丟失ppre_tmp = st.top();if (ppre_tmp->data > pre_tmp->data)ppre_tmp->left = pre_tmp;elseppre_tmp->right = pre_tmp;}}delete tmp;tmp = nullptr;return true;}

源cpp代碼

#include"AVL.h" #include<iostream> using namespace std; int main() {AVLTree<int> tree;cout << "建立AVL樹，終止表示設(shè)為0" << endl;tree.Refvalue = 0;cout << "1:建樹\n2:插入\n3:搜索\n4:刪除\n5:輸出\n6:清空\n7:退出\n";bool over = false;while (!over){int c;int num;cin >> c;switch (c){case 1: {cin >> tree;cout << "建樹完畢\n";break;}case 2: {cin >> num; tree.insert(tree.root, num); cout << "插入完畢\n"; break; }case 3: {cin >> num; if (tree.search(num, tree.root) != NULL)cout << num << "已經(jīng)被找到\n"; else cout << num << "不存在\n"; break; }case 4: {cin >> num; tree.Remove(tree.root, num); }case 5: {cout << tree; cout << " 凹凸打印AVL樹\n"; tree.PrintBinTree(tree.root, 1); break; }case 6: {//tree.Delete(tree.root); tree.root=NULL;break; }case 7:{ over = true; break; }default:cout << "輸入有誤\n";break;}}char ch;cin >> ch; }

轉(zhuǎn)載于:https://www.cnblogs.com/gzr2018/p/10112621.html

總結(jié)

以上是生活随笔為你收集整理的AVL树C++实现（插入，删除，查找，清空，遍历操作）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。