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