AVL树C++实现（插入，删除，查找，清空，遍历操作）

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 << "内存不足" << endl; exit(1); }if (pr == NULL) { ptr = p; return true; }//空树，根结点插入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 << "中序遍历输出各个结点数值:" << 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) //找到跳出循环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; //将有两个孩子的节点转化为只有一个孩子的节点，方法是寻找它中序遍历的直接前驱或后继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; //覆盖要删除的节点tmp = it_tmp; //tmp指向要删除的节点，函数结束前会delete tmp}if (tmp->left!= nullptr) { //这样的判断方式会导致删除一个节点下两个没有孩子节点的节点时，由于左孩子均为空，直接跳入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用来识别是祖父节点的左孩子还是右孩子，下文链接会用上flag = 0;}else {sign = 1;flag = 1;}}elsesign = 0; //栈空，它的祖先节点不存在，pre_tmp即为根节点，但是这里也要写上，否则sign的值会遗留下来if (pre_tmp->bf == -1 || pre_tmp->bf == 1)break; //已经平衡，直接跳出if (pre_tmp->bf != 0) { //m_bf为+2/-2if (pre_tmp->bf < 0) {lable = -1; //lable表示父节点符号，下面会用来区分同号异号it_tmp = pre_tmp->left;}else {lable = 1;it_tmp = pre_tmp->right;}if (it_tmp->bf == 0) { //pre_tmp的较高子树的头节点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()) //栈为空，根节点t = pre_tmp;else { //这一段else参考书上没有，书是错的，如果不写此处，290break直接跳出while循环，会导致链接不上，数据丢失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树，终止表示设为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 << "已经被找到\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; }

转载于:https://www.cnblogs.com/gzr2018/p/10112621.html

总结

以上是生活随笔为你收集整理的AVL树C++实现（插入，删除，查找，清空，遍历操作）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。