AVL_TREE.rar_AVL树

#include <iostream> #include <cstdlib> //生成随机数的头文件 #include <ctime> #include <cmath> //abs函数的头文件 #define N 100 //节点个数 #define MAX 500 //生成节点随机数的最大值 #define MIN 100 //生成节点随机数的最小值 using namespace std; struct node //功能：定义树的节点 { int key; int h;//节点的高度，且初始化为1 node *left; node *right; node *father; node():left(NULL),right(NULL),key(NULL),father(NULL),h(1){} node(int k):left(NULL),right(NULL),key(k),father(NULL),h(1){} }; int high(node *x) { if(x==NULL) return 0; else return (x->h); } int Random(int min,int max) //功能：生成min-max之间的随机数 { return (rand()%(max-min+1)+min); } node *LL_ROTATE(node *x6,node *f)//<右旋转函数> 在左孩子的左子树上的节点 x为节点、f为其父节点 { if(f->father) { node *temp = f->father; if(f == (temp->left) ) (temp->left) = x6 ; else (temp->right) = x6 ; x6->father = f->father ; f->left = x6->right ; (f->left)->father = f ; x6->right = f ; f->father = x6 ; } else { x6->father = NULL ; f->left = x6->right ; (f->left)->father = f ; x6->right = f ; f->father = x6 ; } if( high(x6->left) >= high(x6->right) ) x6->h = high(x6->left) +1; else x6->h = high(x6->right)+1; if( high(f->left) >= high(f->right) ) f->h = high(f->left) +1; else f->h = high(f->right)+1; return x6; } node *RR_ROTATE(node *x5,node *f)//<左旋转函数> 在右孩子的右子树上的节点 x为节点、f为其父节点 返回为需要继续维护的节点 { if(f->father) { node *temp = f->father; if(f == (temp->left) ) (temp->left) = x5 ; else (temp->right) = x5 ; x5->father = f->father; f->right = x5->left ; (f->right)->father = f; x5->left = f ; f->father = x5 ; } else { x5->father = NULL ; f->right = x5->left ; (f->right)->father = f; x5->left = f ; f->father = x5 ; } if( high(x5->left) >= high(x5->right) ) x5->h = high(x5->left) +1; else x5->h = high(x5->right)+1; if( high(f->left) >= high(f->right) ) f->h = high(f->left) +1; else f->h = high(f->right)+1; return x5; } node *LR_ROTATE(node *x4,node *f)//<先左旋再右旋> 在左孩子的右子树上的节点 x为节点、f为其父节点 { node *temp1; node *temp2; node *t; t = x4->right; temp1 = RR_ROTATE(t,x4) ; temp2 = LL_ROTATE(temp1,f); return temp2; } node *RL_ROTATE(node *x3,node *f)//<先右旋再左旋> 在左孩子的右子树上的节点 x为节点、f为其父节点 { node *temp1; node *temp2; node *t; t = x3->left ; temp1 = LL_ROTATE(t,x3) ; temp2 = RR_ROTATE(temp1,f) ; return temp2 ; } node *AVL_BLANCE(node *x2)//功能：维持AVL树平衡 返回维持平衡后新树的根节点t { int hl,hr; node *t ; node *f; t = x2 ; while((t->father) != NULL)//问题在此； { f = t->father ; hl=high(f->left) ; hr=high(f->right) ; if(abs(hl-hr) >= 2) { if( hl > hr ) if(high(t->left) > high(t->right)) t = LL_ROTATE(t,f); else t = LR_ROTATE(t,f); else if(high(t->left) > high(t->right)) t = RL_ROTATE(t,f); else t = RR_ROTATE(t,f); } else { if( high(t->left) >= high(t->right) ) t->h = high(t->left) +1; else t->h = high(t->right)+1; if( high(f->left) >= high(f->right) ) f->h = high(f->left) +1; else f->h = high(f->right)+1; t = f; } } return t; } node* AVL_INSERT(node *tree , node *x1)//功能：插入新节点x到AVL树中 tree表示根节点 返回插入的节点x { node *f = tree; if(x1-> key <= tree->key ) { if( tree->left ) return AVL_INSERT(f->left , x1); else { tree->left = x1 ; x1->father = tree; } return x1; } if(x1-> key > tree->key ) { if( tree->right ) return AVL_INSERT(f->right , x1); else { tree->right = x1 ; x1->father = tree; } return x1; } } void AVL_Printf(node *tree) //输出函数 按大小顺序输出树tree中的数据key { if(tree->left !=NULL) AVL_Printf(tree->left); cout<<tree->key <<'\t'; if(tree->right !=NULL) AVL_Printf(tree->right); } int main() { int i=0; srand(unsigned(time(NULL))); node *pTree = new node(); int j = Random(MIN,MAX) ; node *x = new node(j); cout<<"开始创建AVL树(以下数据为依次插入的节点数据):\n"<<x->key<<"\t" ; pTree = x; for(i=1; i<N ; i++) { int j = Random(MIN,MAX) ;; node *x = new node(j); x = AVL_INSERT(pTree, x); cout<<x->key<<"\t" ; } cout<<"\n由大到小顺序输出AVL树中的数据"<<endl; AVL_Printf(pTree); return 0; }