平衡二叉树-AVL树的实现

#include "AVLTree.h" void AVLTree::Search(Data data) { AVLNode *pr ; if((pr = Search(data, root)) != NULL) { cout<<"找到了数据域为'"<<data<<"'的结点！"<<endl; //cout<<"它的平衡因子是："<<pr->bf<<endl; } else { cout<<"没有找到！"<<endl; return; } } AVLNode *AVLTree::Search(const Data x, AVLNode *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; } void AVLTree::RotateL(AVLNode *& ptr) { AVLNode *subL = ptr; ptr = subL->right; subL->right = ptr->left; ptr->left = subL; ptr->bf = subL->bf = 0; } void AVLTree::RotateR(AVLNode *& ptr) { AVLNode *subR = ptr; ptr = subR->left; subR->left = ptr->right; ptr->right = subR; ptr->bf = subR->bf = 0; } void AVLTree::RotateLR(AVLNode *& ptr) { AVLNode *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; } void AVLTree::RotateRL(AVLNode *& ptr) { AVLNode *subL = ptr, *subR = subL->left; 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; } bool AVLTree::Insert(AVLNode *& ptr, Data& el) { AVLNode *pr = NULL, *p = ptr, *q; int d; stack<AVLNode *> st; while(p != NULL) { if(el == p->data) return false; pr = p; st.push(pr); if(el < p->data) p = p->left; else p = p->right; } p = new AVLNode(el); if(p == NULL) { cout<<"No space anymore!"<<endl; exit(0); } if(pr == NULL) { ptr = p; return true; } if(el < 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; if(pr->bf == 1 || pr->bf == -1) p = pr; else { d = (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; } istream& operator >> (istream& in, AVLTree& Tree) { Data item; char end = Tree.RefValue; cout<<"创建AVL树："<<endl; cout<<"输入数据（以'"<<end<<"'）结束："; in>>item; while(item != Tree.RefValue) { Tree.Insert(item); cout<<"输入数据（以'"<<end<<"'）结束："; cin>>item; } return in; } void AVLTree::inorder(void (*visit)(char &)) { recursive_inorder(root,visit); } void AVLTree::recursive_inorder(AVLNode *sub_root, void (*visit)(char &)) { static int i = -1; //static 表示所有的递归展开式共用一个i int j; //i 就可以用来记录递归的层数 if(sub_root != NULL) { i++; recursive_inorder(sub_root->left, visit); for(j = 0; j < i; j++) cout<<"*"; (*visit)(sub_root->data); recursive_inorder(sub_root->right, visit); i--; } } bool AVLTree::Remove(AVLNode *&ptr, Data& el) { AVLNode *pr = NULL, *p = ptr, *q, *ppr; int d, dd= 0; Data k = el; stack<AVLNode*> st; while(p != NULL) { if(k == p->data) //寻找删除的位置, 找到等于k的节点 break; pr = p; st.push(pr); if(k < p->data) p = p->left; else p = p->right; } if(p == NULL) return false; if(p->left != NULL && p->right != NULL) { pr = p; st.push(pr); q = p->left; while(q ->right != NULL) { pr = q; st.push(pr); q = q->right; } p->data = q->data; p = q; } if(p->left != NULL) q = p->left; else q = p->right; if(pr == NULL) ptr = q; else { if(pr->left == p) pr->left = q; else pr->right = q; while(st.empty() == false) { pr = st.top(); st.pop(); if(pr->right == q) pr->bf--; else pr->bf++; if(st.empty() == false) { ppr = st.top(); dd = (ppr->left == pr) ? -1 : 1; } else dd = 0; if(pr->bf == 1 || pr->bf == -1) break; if(pr->bf != 0) { if(pr->bf < 0) { d = -1; q= pr->left; } else { d = 1; q = pr->right; } if(q->bf == 0) { if(d == 1) { RotateR(pr); pr->bf = 1; pr->left->bf = -1; break; } else { RotateL(pr); pr->bf = -1; pr->right->bf = 1; break; } } if(q->bf == d) { if(d == -1) RotateR(pr); else RotateL(pr); } else { if(d == -1) RotateLR(pr); else RotateRL(pr); } if(dd == -1) ppr->left = pr; else if(dd == 1) ppr->right = pr; } q = pr; } if(st.empty() == true) ptr = pr; } delete p; return true; }