//DSW Algorithm
//我先放二叉树的定义上来，代码丑陋，不要见怪。

 #ifndef BSTREE_H_
#define BETREE_H_

///////////////////////////////////////////////////////////////
//
// File: BSTree.h
//
// This headfile defines BST class to test BSTree.
//
// By tankeryang.
//
// 2015, Dec 2
//
///////////////////////////////////////////////////////////////

#include<iostream>
#include<queue>
#include<stack>

using namespace std;

template<class T>
class Stack:public stack<T>{};

template<class T>
class Queue:public queue<T>{
public:
    T dequeue(){
        T tmp = front();
        queue<T>::pop();
        return tmp;
    };
    void enqueue(T item){
        push(item);
    };
};

class BSTNode{
public:
    int item;
    BSTNode *lchild, *rchild;
    int level;

    BSTNode(){
        lchild = rchild = NULL;
    };
    BSTNode(int i){
        item = i;
        lchild = rchild = NULL;
    };
};

class BSTree:public BSTNode{
protected:
    BSTNode *root;
    int countOfNode;
    int levelOfTree;
public:
    BSTree(){
        root = NULL;
        countOfNode = 0;
        levelOfTree = 0;
    };
    ~BSTree(){};

    int getLevelOfTree();
    void insert(int);
    void breadthFirst();
    //DSW algorithm
    void rotateRight(BSTNode *);
    void creatBackbone();
    void creatPerfectTree();
    //Inorder recurrence algorithm
    void inOrder();
    void inRecurrence(BSTNode *);
    //////
    void visit(BSTNode *node) {
        std::cout << node->item << ' ';
    };
};

#endif

//接下来放DSW的三个函数的定义
//调试的时候，会出现死循环，原因是出在rotateRight(BSTNode *)
//函数，可能判断条件有问题，还有下面的creatPerfectTree()也有问
//题，望高手赐教。要是觉得在下代码实现的太烂，希望能详细说说您的
//理解，不胜感激。

 // DSW Algorithm
void BSTree::rotateRight(BSTNode *pnode){
    // Rotate the left node to the right link list.
    if(pnode->lchild != NULL) {
        BSTNode *tmp = pnode->lchild;
        pnode->lchild = tmp->rchild;
        tmp->rchild = pnode;
        pnode = tmp;
    }
    else if (pnode->lchild == NULL && pnode->rchild->lchild != NULL) {
        BSTNode *flag = pnode;
        pnode = pnode->rchild;
        BSTNode *tmp = pnode->lchild;
        pnode->lchild = tmp->rchild;
        tmp->rchild = pnode;
        flag->rchild = tmp;
        pnode = flag->rchild;
    }
    else
        pnode = pnode->rchild;
};

void BSTree::creatBackbone(){
    BSTNode *pnode = root;
    while(pnode!=NULL)
        rotateRight(pnode);
};

void BSTree::creatPerfectTree(){
    BSTNode *tmp1=root, *tmp2=tmp1->rchild->rchild;
    while(tmp1!=NULL){
        if(tmp2!=NULL && tmp2->rchild!=NULL){
            tmp1->rchild = tmp1->rchild->lchild;
            tmp1->rchild->lchild = tmp1;
            tmp1 = tmp1->rchild;
            tmp1->rchild = tmp1->rchild->rchild;
            tmp2->rchild->lchild = tmp2;
            tmp2->rchild = NULL;
            tmp2 = tmp1->rchild->rchild;
        }
        else
            break;
    }
};