初始化一个平衡二叉树并且向其中插入或删除数据，Aint是插入，Dint是删除。 如：输入A1 A2 A3 IN则是向树中插入，2，3并且以中序遍历输出。
输出的时候一直没结果，求大神指点！
raversal(root->right);
}
void PreOrderTraversal(Node* root)
{
if(root==NULL)
{
cout<<"EMPTY"<<endl;
}
if(root==0)
{
return;
}
cout<<root->data<<endl;
PreOrderTraversal(root->left);
PreOrderTraversal(root->right);
}
void PostOrderTraversal(Node* root)
{
if(root==NULL)
{
cout<<"EMPTY"<<endl;
}
if(root==0)
{
return;
}
PostOrderTraversal(root->left);
PostOrderTraversal(root->right);
cout<<root->data<<endl;
}
void release(Node* root)
{
if(root==0)
{
return;
}
release(root->left);
release(root->right);
delete root;
}
void search(Node*& root,int key,Node**& _result)
{
if(root==0)
{
_result=0;
return;
}
if(key<root->data)
{
search(root->left,key,_result);
}
else if(key==root->data)
{
_result=&root;
return;
}
else
{
search(root->right,key,_result);
}
}
int getBalanceFactor(Node* root)
{
int val;
if(root->left!=0&&root->right!=0)
{
val = root->left->height-root->right->height;
}
else if(root->left!=0)
{
val=root->left->height;
}
else if(root->right!=0)
{
val=root->right->height;
}
return val;
}
void calculateHeight(Node* root)
{
if(root->left!=0&&root->right!=0)
{
root->height=root->left->height>root->right->height?root->left->height+1:root->right->height+1;
}
else if(root->left!=0)
{
root->height=root->left->height+1;
}
else if(root->right!=0)
{
root->height=root->right->height+1;
}
else
{
root->height=1;
}
}
void cwSpin(Node*& root)
{
if(root->left->left==0)
{
Node* mid=root->left;
root->left=root->left->right;
root->left->left=mid;
mid->right=0;
calculateHeight(root->left->left);
calculateHeight(root->left);
}
Node* ori_root=root;
root=root->left;
Node* beta=root->right;
root->right=ori_root;
if(beta!=0)
{
ori_root->left=beta;
}
else
{
ori_root->left=0;
}
calculateHeight(ori_root);
}
void ccwSpin(Node*& root)
{
if(root->right->right==0)
{
Node* mid=root->right;
root->right=root->right->left;
root->right->right=mid;
mid->left=0;
calculateHeight(root->right->right);
calculateHeight(root->right);
}
Node* ori_root=root;
root=root->right;
Node* beta=root->left;
root->left=ori_root;
if(beta!=0)
{
ori_root->right=beta;
}
else
{
ori_root->right=0;
}
calculateHeight(ori_root);
}
bool Aint(Node*& root,int value)
{
if(root==0)
{
if(1<=value<=100)
{
root=new Node;
root->left=0;
root->right=0;
root->data=value;
root->height=1;
return true;
}
else
{
cout<<"error input!"<<endl;
}
}
if(value>root->data)
{
if(!Aint(root->right,value))
{
return false;
}
else
{
int bf=getBalanceFactor(root);
if(bf==-2)
{
ccwSpin(root);
}
}
}
else if(value==root->data)
{
return false;
}
else
{
if(!Aint(root->left,value))
{
return false;
}
else
{
int bf=getBalanceFactor(root);
if(bf==2)
{
cwSpin(root);
}
}
}
calculateHeight(root);
return true;
}
bool Dint(Node*& root,int key)
{
if(root==0)
{
return false;
}
if(key<root->data)
{
if(Dint(root->left,key))
{
calculateHeight(root);
int bf=getBalanceFactor(root);
if(bf==2)
{
cwSpin(root);
}
if(bf==-2)
{
cwSpin(root);
}
calculateHeight(root);
return true;
}
else
{
return false;
}
}
else if(key==root->data)
{
Node* temp=root;
if(root->left==0&&root->right==0)
{
root=0;
delete temp;
}
else if(root->left==0)
{
root=root->right;
delete temp;
}
else if(root->right==0)
{
root=root->left;
delete temp;
}
else
{
Node* s=root->right;
Node* s_parent=root;
stack<Node**>_stack;
_stack.push(&root);
bool first=true;
while(s->left!=0)
{
if(first)
{
_stack.push(&s_parent->right);
}
else
{
_stack.push(&s_parent->left);
}
s_parent=s;
s=s->left;
first=false;
}
temp->data=s->data;
if(s->right!=0)
{
if(s_parent==root)
{
s_parent->right=s->right;
}
else
{
s_parent->left=s->right;
}
}
else
{
if(s_parent==root)
{
s_parent->right=0;
}
else
{
s_parent->left=0;
}
}
while(_stack.size()>0)
{
calculateHeight(*_stack.top());
int bf=getBalanceFactor(*_stack.top());
if(bf==2)
{
cwSpin(*_stack.top());
}
if(bf==-2)
{
ccwSpin(*_stack.top());
}
calculateHeight(*_stack.top());
_stack.pop();
}
delete s;
}
return true;
}
else
{
if(Dint(root->right,key))
{
calculateHeight(root);
int bf=getBalanceFactor(root);
if(bf==2)
{
cwSpin(root);
}
if(bf==-2)
{
ccwSpin(root);
}
calculateHeight(root);
return true;
}
else
{
return false;
}
}
}
int main(int nargs, char argv[])
{
Node root=new Node;
for(int i=1;i<nargs;i++)
{
if(nargs==i-1)
{
if(string(argv[i]) == "IN")
{
InOrderTraversal(root);
}
if(string(argv[i]) == "PRE")
{
PreOrderTraversal(root);
}
if(string(argv[i]) == "POST")
{
PostOrderTraversal(root);
}
}
else
{
string acc;
acc = string(argv[i]);
string a;
int num;
for(int i = 1; i <4; i++)
{
if(!isdigit(acc[2]))
{
num = acc[1] - 48;
}
else if(!isdigit(acc[3]))
{
num = (acc[1] - 48)*10 + (acc[2]-48);
}
else if(!isdigit(acc[4]))
{
num = (acc[1]-48)*100 + (acc[2] - 48)*10 + (acc[3]-48);
}
}
a = acc[0];
if(a == "A")
{
Aint(root,num);
}
else if(a == "D")
{
Dint(root,num);
}
}
}
release(root);
return 0;
}
