您的位置: 首页  >  文章  >  树的左旋与右旋

树的左旋与右旋

分类: 文章 • 2024-06-05 18:20:10


下图所示操作称为对结点Q的右旋，对结点P的左旋。二者互为逆操作。

简单讲，右旋——自己变为左孩子的右孩子；左旋——自己变为右孩子的左孩子。


树的左旋与右旋

[cpp] view plain copy
  1. #include  
  2.   
  3. class BinTree{  
  4. private:  
  5.     typedef struct node{  
  6.         int data;  
  7.         node*lchild,*rchild,*parent;  
  8.     }*tree;  
  9.     tree root;  
  10. public:  
  11.     void right_rotate(node *p);  
  12.     void left_rotate(node *p);  
  13. };  
  14. void BinTree::right_rotate(node *q){  
  15.       
  16.     node* p=q->lchild;  
  17.     node* b=p->rchild;  
  18.     node* fa=q->parent;  
  19.       
  20.     b->parent=q;  
  21.     q->lchild=b;  
  22.   
  23.     q->parent=p;  
  24.     p->rchild=q;  
  25.   
  26.     if(q==root)  
  27.         root=p;//此时p->parent==q 但没关系，已经标记了根为p  
  28.     else{  
  29.         p->parent=fa;  
  30.         if(fa->lchild==q) fa->lchild=p;  
  31.         else fa->rchild=p;  
  32.     }  
  33. }  
  34. void BinTree::left_rotate(node *p){  
  35.     tree q=p->rchild;  
  36.     tree b=q->lchild;  
  37.     node* fa=p->parent;  
  38.   
  39.     b->parent=p;  
  40.     p->rchild=b;  
  41.   
  42.     p->parent=q;  
  43.     q->lchild=p;  
  44.   
  45.     if(p==root)  
  46.         root=q;//此时q->parent==p 但没关系，已经标记了根为q  
  47.     else{  
  48.         q->parent=fa;  
  49.         if(fa->lchild==p) fa->lchild=q;  
  50.         else fa->rchild=q;  
  51.     }  
  52.   
  53. }  

下图所示操作称为对结点Q的右旋，对结点P的左旋。二者互为逆操作。

简单讲，右旋——自己变为左孩子的右孩子；左旋——自己变为右孩子的左孩子。


树的左旋与右旋

[cpp] view plain copy
  1. #include  
  2.   
  3. class BinTree{  
  4. private:  
  5.     typedef struct node{  
  6.         int data;  
  7.         node*lchild,*rchild,*parent;  
  8.     }*tree;  
  9.     tree root;  
  10. public:  
  11.     void right_rotate(node *p);  
  12.     void left_rotate(node *p);  
  13. };  
  14. void BinTree::right_rotate(node *q){  
  15.       
  16.     node* p=q->lchild;  
  17.     node* b=p->rchild;  
  18.     node* fa=q->parent;  
  19.       
  20.     b->parent=q;  
  21.     q->lchild=b;  
  22.   
  23.     q->parent=p;  
  24.     p->rchild=q;  
  25.   
  26.     if(q==root)  
  27.         root=p;//此时p->parent==q 但没关系，已经标记了根为p  
  28.     else{  
  29.         p->parent=fa;  
  30.         if(fa->lchild==q) fa->lchild=p;  
  31.         else fa->rchild=p;  
  32.     }  
  33. }  
  34. void BinTree::left_rotate(node *p){  
  35.     tree q=p->rchild;  
  36.     tree b=q->lchild;  
  37.     node* fa=p->parent;  
  38.   
  39.     b->parent=p;  
  40.     p->rchild=b;  
  41.   
  42.     p->parent=q;  
  43.     q->lchild=p;  
  44.   
  45.     if(p==root)  
  46.         root=q;//此时q->parent==p 但没关系，已经标记了根为q  
  47.     else{  
  48.         q->parent=fa;  
  49.         if(fa->lchild==p) fa->lchild=q;  
  50.         else fa->rchild=q;  
  51.     }  
  52.   
  53. }  

相关推荐