#include <iostream>
#include <string>
using namespace std;
template <class T>
struct BSTNode
{
BSTNode *left,*right;
T element;
BSTNode(BSTNode* x=0,BSTNode* y=0,T e=T())
{
left=x;
right=y;
element=e;
}
};
/////////////////////////////////////////////////////////////
//普通二叉树类
/////////////////////////////////////////////////////////////
template <class T>
class SPTree
{
public:
SPTree(){root=NULL;}
BSTNode<T>* get_root();
bool is_digit(string x);
BSTNode<T>* LRot(BSTNode<T>* node);//单左旋转
BSTNode<T>* RRot(BSTNode<T>* node);//单右旋转
BSTNode<T>* LLRot(BSTNode<T>* node);//左左双旋转
BSTNode<T>* RRRot(BSTNode<T>* node);//右右双旋转
BSTNode<T>* LRRot(BSTNode<T>* node);//左右双旋转
BSTNode<T>* RLRot(BSTNode<T>* node);//右左双旋转
BSTNode<T>* insert(BSTNode<T>* node,T x);
void print_data(T& data,int level); //输出二叉树
void print_tree(BSTNode<T>* node,int level);
BSTNode<T>* input(istream& in); //输入二叉树
void SPTree<T>::output(ostream& out);
~SPTree(){delete root;}
private:
BSTNode<T>* root;
};
template <class T>
BSTNode<T>* SPTree<T>::LRot(BSTNode<T>* node)//单左旋转
{
/*
p q
/ \ / \
q R ---------> A p
/\ / \
A B B R
*/
BSTNode<T>* temp=node->left;
node->left=temp->right;
temp->right=node;
return temp;
}
template <class T>
BSTNode<T>* SPTree<T>::RRot(BSTNode<T>* node)//单右旋转
{
/*
p q
/ \ / \
q R <--------- A p
/\ / \
A B B R
*/
BSTNode<T>* temp=node->right;
node->right=temp->left;
temp->left=node;
return temp;
}
template <class T>
BSTNode<T>* SPTree<T>::LLRot(BSTNode<T>* node)//左左双旋转
{
/*
p r
/ \ / \
q R ---------> A q
/\ / \
r C B p
/ \ / \
A B C R
*/
BSTNode<T>* temp1=node->left;
BSTNode<T>* temp2=temp1->left;
temp1->left=temp2->right;
node->left=temp1->right;
temp2->right=temp1;
temp1->right=node;
return temp2;
}
template <class T>
BSTNode<T>* SPTree<T>::RRRot(BSTNode<T>* node)//右右双旋转
{
/*
p r
/ \ / \
q R <--------- A q
/\ / \
r C B p
/ \ / \
A B C R
*/
BSTNode<T>* temp1=node->right;
BSTNode<T>* temp2=temp1->right;
temp1->right=temp2->left;
node->right=temp1->left;
temp2->left=temp1;
temp1->left=node;
return temp2;
}
template <class T>
BSTNode<T>* SPTree<T>::LRRot(BSTNode<T>* node)//左右双旋转
{
/*
p r
/ \ / \
q R ---------> q p
/\ / \ / \
A r A B C R
/ \
B C
*/
BSTNode<T>* temp1=node->left;
BSTNode<T>* temp2=temp1->right;
temp1->right=temp2->left;
node->left=temp2->right;
temp2->left=temp1;
temp2->right=node;
return temp2;
}
template <class T>
BSTNode<T>* SPTree<T>::RLRot(BSTNode<T>* node)//右左双旋转
{
/*
p r
/ \ / \
R q --------> p q
/\ / \ / \
r A R B C A
/ \
B C
*/
BSTNode<T>* temp1=node->right;
BSTNode<T>* temp2=temp1->left;
temp1->left=temp2->right;
node->right=temp2->left;
temp2->right=temp1;
temp2->left=node;
return temp2;
}
template <class T>
BSTNode<T>* SPTree<T>::insert(BSTNode<T>* node,T x)
{
BSTNode<T>* r=NULL;
BSTNode<T>* result=NULL;
if(node==NULL) //是新结点
{
result=new BSTNode<T>(0,0,x);
return result;
}
else if(x<node->element)//插入左子树
{
r=node->left;
if(r==NULL) //插入
{
r=new BSTNode<T>(0,0,x);
r->right=node;
node->left=NULL;
return r;
}
else if(x==r->element)//结点已经存在
{
result=LRot(node); //单旋转
return result;
}
else if(x<r->element)//插入左结点的左子树
{
r->left=insert(r->left,x);
r=LRot(r); //双旋转 LL
node->left=r;
}
else if(x>r->element)//插入左结点的右子树
{
r->right=insert(r->right,x);
r=RRot(r); //双旋转LR
node->left=r;
}
result=LRot(node);
}
else //插入右子树
{
r=node->right;
if(r==NULL) //插入
{
result=new BSTNode<T>(0,0,x);
result->left=node;
node->right=NULL;
return result;
}
else if(x==r->element) //结点已经存在
{
result=RRot(node); //单旋转
return result;
}
else if(x<r->element) //插入右结点的左子树
{
r->left=insert(r->left,x);
r=LRot(r); //双旋转 RL
node->right=r;
}
else if(x>r->element) //插入右结点的右子树
{
r->right=insert(r->right,x);
r=RRot(r); //双旋转 RR
node->right=r;
}
result=RRot(node);
}
return result;
}
template <class T>
void SPTree<T>::print_data(T& data,int level)
{
for(int i=0;i<level;i++)
cout<<" ";
cout<<data<<endl;
}
template <class T>
void SPTree<T>::print_tree(BSTNode<T>* node,int level)
{
if(node!=NULL)
{
if(node->right!=NULL)
print_tree(node->right,level+1);
print_data(node->element,level);
if(node->left!=NULL)
print_tree(node->left,level+1);
}
}
template <class T>
BSTNode<T>* SPTree<T>::get_root()
{
return root;
}
template <class T>
bool SPTree<T>::is_digit(string x)
{
char* temp=(char*)calloc(20,sizeof(char));
strcpy(temp,x.c_str());
for(int i=0;i<x.size();i++)
{
char y=temp[i];
if(y<'0'||y>'9')
break;
return true;
}
return false;
}
template <class T>
BSTNode<T>* SPTree<T>::input(istream& in)
{
string x;
int e;
while(true)
{
in>>x;
if(is_digit(x))
e=atoi(x.c_str());
else
break;
root=insert(root,e);
}
return root;
}
template <class T>
void SPTree<T>::output(ostream& out)
{
out<<"the tree contains is as follows"<<endl;
print_tree(root,0);
}
int main()
{
SPTree<int>* x=new SPTree<int>();
x->input(cin);
x->output(cout);
system("pause");
}
