#include<iostream>#include<stdlib.h>#include<math.h>using namespace std;class Node{	public:	int el;	Node *left,*right;	Node(){		left=0;right=0;	}	Node(int data){		el = data;left=0;right=0;	}};class Tree{public:	Node *root;						Tree(){		root=0;size=0;	}	Tree(int el){		root=new Node(el);size=1;	}	void insert(int el){		Node *ins = new Node(el),*tmp=root,*par;		if(tmp==0){			root = ins;			size++;			return;		}		while(tmp!=0){			par = tmp;			if(tmp->el>el)tmp = tmp->left;			else tmp = tmp->right;		}		if(par->el>el)			par->left = ins;		else 			par->right = ins;		size++;	}		//  转换成右链	void creatBackbone(){		Node *Gr=0,*par=root,*ch=0;		while(par!=0){			ch = par->left;			if(ch!=0){				rotateRight(Gr,par,ch);				par=ch;			}else{				Gr=par;				par=par->right;			}			// 旋转过程中，如果是绕根节点的右节点旋转时要将根节点置为原根节点的右节点			if(Gr==0)root = ch;		}	}		void rotateRight(Node *Gr,Node *par,Node *ch){				if(Gr!=0)Gr->right=ch;		par->left=ch->right;		ch->right=par;	}	// 平衡二叉树	void creatPerfectTree(){		int n = size;		int m = (1<<((int)(log10(n+1)/log10(2))))-1;		int i;		Node *Gr=0,*tmp;		if(size<3)return;printf("%d\n",m);		for(i=0,Gr=root;i<n-m;i++){			if(i==0){				// 此处Gr是旋转时被绕的节点的祖父节点，下边以Gr->right传引用方便旋转函数赋值操作				Gr = Gr->right;				rotateLeft(root);				}else if(Gr&&Gr->right){				// 提前保存下次绕点的祖父节点，旋转后它们之间关系被破坏				tmp = Gr->right->right;				rotateLeft(Gr->right);				Gr = tmp;			}		}		while(m>1){			m = m/2;			for(i=0,Gr=root;i<m;i++){				if(i==0){					Gr = Gr->right;					rotateLeft(root);				}else if(Gr&&Gr->right){					tmp = Gr->right->right;					rotateLeft(Gr->right);					Gr = tmp;				}			}		}	}	void rotateLeft(Node *&Gr){		if(!Gr) return;		Node *par = Gr->right;		if(!par)return;		Node *ch  = par->right;		Gr->right=par->left;		par->left=Gr;		Gr = par;	}private:	int size;};int main(){		int a[] = {0,3,4,5,6,1,2,7,11,12,8,9,10,13,14};	int i;	Tree *tree = new Tree();	for(i=0;i<15;i++){		tree->insert(a[i]);	}	tree->creatBackbone();	tree->creatPerfectTree();	return 0;}