平衡二叉树DSW算法

#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;
}