//------------BST.h-----

#include <iostream>
using namespace std;

#ifndef _BST_H
#define _BST_H

template< class T >
class BSTNode
{
    public:
        BSTNode():key(0),left(0),right(0) {}
        BSTNode( const T& el , BSTNode<T> *l = 0 , BSTNode<T> *r = 0 ):key(el),left(l),right(r) {}
    
        T key;
        BSTNode<T> *left ,*right;
};

template< class T >
class BST
{
    public:
        BST():root(0) {}
        
        void insert( const T &el );

        void preorder( BSTNode<T> *p );
        void DSW();


        BSTNode<T> * getroot() { return root; }
    private:
                  //衵唅蛌誹萸
        BSTNode<T> * Rotateright( BSTNode<T> *gr , BSTNode<T> *pr ,BSTNode<T> *ch );
                  //酘唅蛌誹萸
        BSTNode<T> * Rotateleft( BSTNode<T> *gr , BSTNode<T> *pr ,BSTNode<T> *ch );
                  //數呾郔諉輪誹萸杅 n 腔雛媼脫攷腔誹萸跺杅
        int nodenumber( int n );
                  //植跦誹萸羲宎ㄛ砃酘唅蛌 n 棒
        void left_n_times( int n );

        BSTNode<T> *root;
        void visit( const BSTNode<T> *p ){ cout << " " << p->key ; }
};

template<class T>
void BST<T>::insert( const T &el )
{
    BSTNode<T> *p = root , *prev  = root ;

    if( root == 0 )
    {
        root = new BSTNode<T>(el);
        return;
    }
    while( p != 0 )
    {
        prev = p;
    
        if( p->key >el )
        {
            p = p->left;
        }
        else p = p->right;
    }
    if( prev->key > el )
        prev->left = new BSTNode<T>(el);
    else
        prev->right = new BSTNode<T>(el);
}


template<class T>
void BST<T>::preorder( BSTNode<T> *p )
{
    if( p != 0 )
    {
        visit(p);
        preorder( p->left );
        preorder( p->right );
    }
}

template < class T >
BSTNode<T> * BST<T>::Rotateright( BSTNode<T> *gr , BSTNode<T> *pr ,BSTNode<T> *ch )
{
    if( pr != root )
        gr->right = pr->left;
    else
        root = pr->left;
    pr->left = ch->right;
    ch->right = pr;
    return ch;
}

template < class T >
BSTNode<T> * BST<T>::Rotateleft( BSTNode<T> *gr , BSTNode<T> *pr ,BSTNode<T> *ch )
{
    if( pr != root )
        gr->right = pr->right;
    else
        root = pr->right;
    pr->right = ch->left;
    ch->left = pr;
    return ch;
}

template < class T >
void BST<T>::DSW()
{
    BSTNode<T> *tmp =root, *prev = root;

    while( tmp != 0 )
    {
        if( tmp->left )
            tmp = Rotateright( prev , tmp ,tmp->left );
        else
        {
            prev = tmp;
            tmp = tmp->right;
        }
    }
    //计算节点个数 i
    int i = 0 ;
    for( tmp = root ; tmp != 0 ; tmp = tmp->right , i++ );
    
    // m = 最接近节点个数 i 的满二叉树的节点数
    int m = nodenumber(i);
    left_n_times( i-m );  //

    while( m != 0 )
    {
        m = m/2;
        left_n_times( m );
    }
}

template < class T >
void BST<T>::left_n_times( int n )
{
    BSTNode<T> *tmp =root, *prev = root;

    for( ; n > 0 ; n-- )
    {
        tmp = Rotateleft( prev , tmp ,tmp->right );
        prev = tmp;
        tmp = tmp->right;
    }
}

template < class T >
int BST<T>::nodenumber( int n )
{
    int tmp = 0 , k =1;
    while( tmp <= n)
    {
        tmp = (1 << k) - 1;
        k++;
    }

    return tmp>>1;
}

#endif


#include "BST.h"

//------------------------main.cpp
int main()
{
    BST<int> a;

    a.insert(7);
    a.insert(15);
    a.insert(10);
    a.insert(5);
    a.insert(6);
    a.insert(11);
    a.insert(2);
    a.insert(17);
    a.insert(8);

    a.DSW();
    a.preorder(a.getroot());
    cout<<endl;
    cout<<endl;
    return 0;
}