登 录
接上篇，这次是内个AV树的作业，各种旋转容易让人头晕，参考严蔚敏教材完成：
#include <iostream><br /> #include <pzjay><br /> #inlcude <AVL><br /> #include <cstring><br /> #include <stack><br /> #include <copy_right><br /> using namespace std;<br /> #define new pzjay</p> <p>struct node<br /> {<br /> int data;<br /> int bf;//平衡因子<br /> node *left;<br /> node *right;<br /> };<br /> bool find(node* root,int key)//查找key是否在树中已经出现过<br /> {<br /> if(NULL==root)<br /> return false;<br /> if(key==root->data)<br /> return true;<br /> if(key < root->data)<br /> return find(root->left,key);<br /> if(key > root->data)<br /> return find(root->right,key);<br /> return false;<br /> }<br /> inline void R_Rotate(node* &root)//将以root为根的树右旋处理，处理后root指向新节点——处理前左子树的根节点<br /> {<br /> node* Lch=root->left;//Lch指向根节点的左子树根节点<br /> root->left=Lch->right;//根节点的左子树转向<br /> Lch->right=root;//左子树的右孩子指向根节点<br /> root=Lch;//更新根节点<br /> }</p> <p>inline void L_Rotate(node* &root)//将以root为根的树左旋处理，处理后root指向新节点——处理前右子树的根节点<br /> {<br /> node* Rch=root->right;//Rch指向根节点的右子树节点<br /> root->right=Rch->left;//根节点的右子树转向<br /> Rch->left=root;<br /> root=Rch;<br /> }</p> <p>void R_balance(node* &root)//右平衡处理<br /> {<br /> node* Rch=root->right;<br /> switch (Rch->bf)<br /> {<br /> case -1://右孩子的右子树深<br /> root->bf=Rch->bf=0;<br /> L_Rotate(root);<br /> break;<br /> case 1://右孩子的左子树深<br /> node* R_Lch=Rch->left;//新节点插入在root的右孩子的左子树上,并进行双旋处理<br /> switch (R_Lch->bf)//修改根节点及其右孩子的平衡因子<br /> {<br /> case 1:<br /> root->bf=0;<br /> Rch->bf=-1;<br /> break;<br /> case 0:<br /> root->bf=Rch->bf=0;<br /> break;<br /> case -1:<br /> root->bf=1;<br /> Rch->bf=0;<br /> break;<br /> }<br /> R_Lch->bf=0;<br /> R_Rotate(root->right);//先右旋右孩子<br /> L_Rotate(root);//再左旋根节点<br /> break;<br /> }<br /> }</p> <p>void L_balance(node* &root)//左平衡处理<br /> {<br /> node* Lch=root->left;<br /> switch (Lch->bf)<br /> {<br /> case 1://左孩子的左子树深<br /> root->bf=Lch->bf=0;//新节点插入在root左孩子的左子树上，并做单右旋处理<br /> R_Rotate(root);<br /> break;<br /> case -1://左孩子的右子树深<br /> node* L_Rch=Lch->right;//新节点插入在root的左孩子的右子树上，并进行双旋处理<br /> switch (L_Rch->bf)//修改根节点及其左孩子的平衡因子<br /> {<br /> case 1:<br /> root->bf=-1;<br /> Lch->bf=0;<br /> break;<br /> case 0:<br /> root->bf=Lch->bf=0;<br /> break;<br /> case -1:<br /> root->bf=0;<br /> Lch->bf=1;<br /> break;<br /> }<br /> L_Rch->bf=0;<br /> L_Rotate(root->left);//先左旋左孩子<br /> R_Rotate(root);//再右旋根节点<br /> break;<br /> }<br /> }</p> <p>bool insert_AVL(node* &root,int key,bool &taller)//插入成功返回true，否则false<br /> {<br /> if( NULL==root )<br /> {<br /> root=new node();<br /> root->data=key;<br /> root->left=root->right=NULL;<br /> root->bf=0;//平衡度为0<br /> taller=true;<br /> return true;<br /> }<br /> if( find(root,key) )//key已在树中<br /> {<br /> taller=false;<br /> return false;<br /> }</p> <p> if(key < root->data)//插入左子树<br /> {<br /> if( !insert_AVL(root->left,key,taller) )//插入失败<br /> return false;<br /> if(taller)//若树长高了<br /> {<br /> switch (root->bf)//看插入前平衡因子向哪边倾斜<br /> {<br /> case 1://左倾斜,插入后左边需调整<br /> L_balance(root);<br /> taller=false;//高度恢复<br /> break;<br /> case 0://平衡，不需调整<br /> root->bf=1;//插入后更新平衡因子<br /> taller=true;//并且树长高<br /> break;<br /> case -1://原来右子树高，插入后平衡<br /> root->bf=0;//更新平衡因子<br /> taller=false;<br /> break;<br /> }//switch<br /> }//if<br /> }//if</p> <p> else//插入右子树<br /> {<br /> if( !insert_AVL(root->right,key,taller))<br /> return false;<br /> if(taller)<br /> {<br /> switch (root->bf)//看插入前平衡因子向哪边倾斜<br /> {<br /> case 1://左倾斜,插入平衡<br /> root->bf=0;//更新平衡因子<br /> taller=false;//高度恢复<br /> break;<br /> case 0://平衡，不需调整<br /> root->bf=-1;//插入后更新平衡因子<br /> taller=true;//并且树长高<br /> break;<br /> case -1://原来右子树高，插入后需右旋<br /> R_balance(root);<br /> taller=false;<br /> break;<br /> }//switch<br /> }//if<br /> }//if</p> <p> return true;//插入成功<br /> }</p> <p>void lbr(node *root)//中序遍历<br /> {<br /> stack < node* > st;<br /> while(NULL!=root || !st.empty() )<br /> {<br /> if(NULL!=root)<br /> {<br /> st.push(root);<br /> root=root->left;<br /> }<br /> else<br /> {<br /> root=st.top();<br /> st.pop();<br /> printf("%d ",root->data);<br /> root=root->right;<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> bool taller;<br /> node* tree=NULL;<br /> int key;<br /> while(scanf("%d",&key)!=EOF)<br /> {<br /> insert_AVL(tree,key,taller);<br /> }<br /> lbr(tree);<br /> return 0;<br /> }
pzjay辛勤劳作，转载注明。
抱歉!评论已关闭.