平衡二叉树的相关问题

初始化一个平衡二叉树并且向其中插入或删除数据，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;

}

#include
#include
#include
using namespace std;
struct Node{
int data;
int height;
Node* left;
Node* right;
}Note;
void InOrderTraversal(Node* root){
if(root==NULL){
cout<<"EMPTY"< }
if(root==0){
return;
}
InOrderTraversal(root->left);
cout<data< InOrderTraversal(root->right);
}
void PreOrderTraversal(Node* root){
if(root==NULL){
cout<<"EMPTY"< }
if(root==0){
return;
}
coutdata< PreOrderTraversal(root->left);
PreOrderTraversal(root->right);
}
void PostOrderTraversal(Node* root){
if(root==NULL){
cout<<"EMPTY"< }
if(root==0){
return;
}
PostOrderTraversal(root->left);
PostOrderTraversal(root->right);
cout<data< }
void release(Node* root){
if(root==NULL){
return;
}
release(root->left);
release(root->right);
delete root;
}
void search(Node*& root,int key,Node**& _result){
if(root==0){
_result=0;
return;
}
if(keydata){
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==NULL){
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!"< }
}
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(keydata){
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_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 argc, char* argv[]){ //这里参数
Node root=NULL; //这里是指针,然后这里先指空，方便根节点插入
for(int i=1;i<argc;i++){//argv
if(argc-1==i){ //这里是标记是否为最后一个查询字符
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]);
char a; //这里用字符好一些
int num=0;
//这个地方你是想提取数字吧。没太看懂你的写法我重写了下
for(int j = 1; j <acc.length(); j++){ //这里i和外面循环重复使用了换成了j
if(isdigit(acc[j])){
num=num*10+(acc[j]-48);
}
/*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;
}

这行肯定是不对的，if(nargs==i-1)，应该

 if(nargs-1==i)

改完这行，再补全Node定义，输出如下：

$ ./dist/Debug/GNU-MacOSX/testprj A1 A2 A3 IN
EMPTY
0
EMPTY
1
EMPTY
2
EMPTY
3
EMPTY