Source Code

Problem: 2418  User: lizeliang 
Memory: N/A  Time: N/A 
Language: C++  Result: Runtime Error 

Source Code 

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>

using namespace std;

class avl
{
    private:
        struct node
        {
            char s[50];
            int number;
            int bf;
            node * left,* right;
        };
        node * root;
        int sum;
    public:
        void insert(char *);
        void insertIntoAVL(node * & root,node * & newNode,bool isTaller);
        void rotateToLeft(node * & root);
        void rotateToRight(node * & root);
        void fromLeft(node * & root);
        void fromRight(node * & root);
        void in_travel(node * root);
        void travel();
        avl();
        ~avl();
        void remove(node * root);
};
void avl::insert(char * s)
{
    sum++;
    bool isTaller=true;
    node * newNode;
    newNode=new node;
    strcpy(newNode->s,s);
    newNode->number=1;
    newNode->bf=0;
    newNode->right=newNode->left=NULL;
    insertIntoAVL(root,newNode,isTaller);
}
void avl::insertIntoAVL(node * & root,node * & newNode,bool isTaller)
{
    if(root==NULL)
    {
        root=newNode;
        isTaller=true;
    }
    else
    {
        if(strcmp(root->s,newNode->s)==0)
        {
            root->number++;
            delete(newNode);
        }
            
        else if(strcmp(root->s,newNode->s)>0)
        {
            insertIntoAVL(root->left,newNode,isTaller);
            if(isTaller)
            {
                switch(root->bf)
                {
                    case -1:
                        fromLeft(root);
                        isTaller=false;
                        break;
                    case  0:
                        root->bf=-1;
                        isTaller=true;
                        break;
                    case  1:
                        root->bf=0;
                        isTaller=false;
                        break;
                }   
            }
        }
        else
        {
            insertIntoAVL(root->right,newNode,isTaller);
            if(isTaller)
            {
                switch(root->bf)
                {
                    case -1:
                        root->bf=0;
                        isTaller=false;
                        break;
                    case  0:
                        root->bf=1;
                        isTaller=true;
                        break;
                    case  1:
                        fromRight(root);
                        isTaller=false;
                        break;
                }
            }
        }
    }
}
void avl::fromRight(node * &root)
{
    node * p,* w;
    p=root->right;
    switch(p->bf)
    {
        case 1:
            root->bf=0;
            p->bf=0;
            rotateToLeft(root);
            break;
        case  -1:
            w=p->left;
            switch(w->bf)
            {
                case 1:
                    root->bf=-1;
                    p->bf=0;
                    break;
                case  0:
                    root->bf=0;
                    p->bf=0;
                    break;
                case  -1:
                    root->bf=0;
                    p->bf=1;
                w->bf=0;
                rotateToRight(p);
                root->right=p;
                rotateToLeft(root);
            }
    }
}
void avl::fromLeft(node * &root)
{
    node * p,* w;
    p=root->left;
    switch(p->bf)
    {
        case -1:
            root->bf=0;
            p->bf=0;
            rotateToRight(root);
            break;
        case  1:
            w=p->right;
            switch(w->bf)
            {
                case -1:
                    root->bf=1;
                    p->bf=0;
                    break;
                case  0:
                    root->bf=0;
                    p->bf=0;
                    break;
                case  1:
                    root->bf=0;
                    p->bf=-1;
                w->bf=0;
                rotateToLeft(p);
                root->left=p;
                rotateToRight(root);
            }
    }
}
void avl::rotateToLeft(node * & root)
{
    node * p=root->right;
    root->right=p->left;
    p->left=root;
    root=p;
}
void avl::rotateToRight(node * & root)
{
    node * p=root->left;
    root->left=p->right;
    p->right=root;
    root=p;
}
avl::avl()
{
    root=NULL;
    sum=0;
}
avl::~avl()
{
    remove(root);
}
void avl::remove(node * root)
{
    if(root)
    {
        remove(root->left);
        remove(root->right);
        delete(root);
    }
}
void avl::travel()
{
    in_travel(root);
}
void avl::in_travel(node * root)
{
    double per;
    if(root)
    {
        per=100*(double)root->number/(double)sum;
        in_travel(root->left);
        cout<<root->s<<" "
        <<setiosflags(ios::fixed)<<setprecision(4)
        <<per<<endl;
        in_travel(root->right);
    }
}
int main()
{
    char s[100];
    int i;
    avl li;
    /*for(i=0;i<3;i++)
    {
        scanf("%s",s);
        li.insert(s);
    }*/
    while(gets(s))
        li.insert(s);
    li.travel();
    //system("pause");
    return 0;
}