树的左旋与右旋
下图所示操作称为对结点Q的右旋,对结点P的左旋。二者互为逆操作。
简单讲,右旋——自己变为左孩子的右孩子;左旋——自己变为右孩子的左孩子。
- #include
- class BinTree{
- private:
- typedef struct node{
- int data;
- node*lchild,*rchild,*parent;
- }*tree;
- tree root;
- public:
- void right_rotate(node *p);
- void left_rotate(node *p);
- };
- void BinTree::right_rotate(node *q){
- node* p=q->lchild;
- node* b=p->rchild;
- node* fa=q->parent;
- b->parent=q;
- q->lchild=b;
- q->parent=p;
- p->rchild=q;
- if(q==root)
- root=p;//此时p->parent==q 但没关系,已经标记了根为p
- else{
- p->parent=fa;
- if(fa->lchild==q) fa->lchild=p;
- else fa->rchild=p;
- }
- }
- void BinTree::left_rotate(node *p){
- tree q=p->rchild;
- tree b=q->lchild;
- node* fa=p->parent;
- b->parent=p;
- p->rchild=b;
- p->parent=q;
- q->lchild=p;
- if(p==root)
- root=q;//此时q->parent==p 但没关系,已经标记了根为q
- else{
- q->parent=fa;
- if(fa->lchild==p) fa->lchild=q;
- else fa->rchild=q;
- }
- }
下图所示操作称为对结点Q的右旋,对结点P的左旋。二者互为逆操作。
简单讲,右旋——自己变为左孩子的右孩子;左旋——自己变为右孩子的左孩子。
- #include
- class BinTree{
- private:
- typedef struct node{
- int data;
- node*lchild,*rchild,*parent;
- }*tree;
- tree root;
- public:
- void right_rotate(node *p);
- void left_rotate(node *p);
- };
- void BinTree::right_rotate(node *q){
- node* p=q->lchild;
- node* b=p->rchild;
- node* fa=q->parent;
- b->parent=q;
- q->lchild=b;
- q->parent=p;
- p->rchild=q;
- if(q==root)
- root=p;//此时p->parent==q 但没关系,已经标记了根为p
- else{
- p->parent=fa;
- if(fa->lchild==q) fa->lchild=p;
- else fa->rchild=p;
- }
- }
- void BinTree::left_rotate(node *p){
- tree q=p->rchild;
- tree b=q->lchild;
- node* fa=p->parent;
- b->parent=p;
- p->rchild=b;
- p->parent=q;
- q->lchild=p;
- if(p==root)
- root=q;//此时q->parent==p 但没关系,已经标记了根为q
- else{
- q->parent=fa;
- if(fa->lchild==p) fa->lchild=q;
- else fa->rchild=q;
- }
- }