/*系统环境：centos 5.8
 *
 *
 */
#include
#include
#define MAXSIZE 200
struct node
{
    int score;
    struct node *left;
    struct node *right;
};


struct tree
{
    int count;
    struct node *root;
};
struct tree *create_tree()
{
    struct tree *t;
    t=(struct tree*)malloc(sizeof (struct tree) );
    t->count=0;
    t->root=NULL;
    return t;
}

void inseart_tree(struct tree *t, int score)
{
    if(t->count==0)
    {
        struct node* n;
        n=(struct node*)malloc(sizeof (struct node) );
        n->score=score;
        n->left=NULL;
        n->right=NULL;

        t->count++;
        t->root=n;
    }
    else
    {
        struct node * n;
        struct node * p;
        int tmp;
        tmp=t->count;
        p=t->root;
        n=(struct node*)malloc(sizeof (struct node) );
        n->score=score;
        while(1)
        {   

            if(p->score > n->score)
            {
                if(p->left==NULL)
                {
                    p->left=n;
                    t->count++;
                    break;
                }
                p=p->left;

            }else if(p->score score)
            {
                if(p->right==NULL)
                {
                    p->right=n;
                    t->count++;
                    break;
                }
                p=p->right;
            }
            continue;

        }
    }
}
/*search*/
int search(struct tree *t, int score)
{
    struct node * p;
    p=t->root;
    while(1)
    {

        if(p->score==score)
        {
            printf("The score is%d\n",p->score);
            break;
        }else if(p->score > score)
        {
            if(p->left==NULL)
            {
                break;
            }
            p=p->left;

        }else
        {
            if(p->right==NULL)
            {
                break;
            }
            p=p->right;
        }
        continue;
    }
    return 0;
}
void delete_tree(struct tree *t,int score)
{
    struct node *p,*f,*s,*q;
    int flag,flag2;
    flag=flag2=0;
    p=t->root;
    while((p!=NULL)&&(!flag2))
    {
        if(p->score==score)
            flag2=1;
        else if(p->score>score)
        {
            f=p;
            p=p->left;
        }else
        {
            f=p;
            p=p->right;
        }

    }
    if(flag2)
    {
        if((p->left==NULL)||(p->right==NULL))
        {
            if(p->left==NULL)
            {
                if(p==t->root)
                    t->root=p->right;
                else
                {
                    s=p->right;
                    flag=1;
                }
            }
        }
        else
        {
            q=p;
            s=q->right;
            while(s->left!=NULL)
            {
                q=s;
                s=s->left;
            }
            s->left=p->left;
            if(q!=p)
            {
                q->left=s->right;
                s->right=p->right;
            }
            if(q==p)
                t->root=s;
            else
                flag=1;
        }
        if(flag)
        {
            if(p==f->left)
                f->left=s;
            else
                f->right=s;
        }
        free(p);

    }
    else
        printf("Don't have the node\n");

}
/*遍历二叉树*/
void traversing_binary_tree( struct tree *t)
{
    struct node *stack[MAXSIZE], *p;
    p=t->root;
    int top = -1;
    if (p!= NULL)
    {
        /* 根节点入栈 */
        top++;
        stack[top] = p;
        /* 栈不空时循环 */
        while (top > -1)
        {
            /* 出栈并访问该节点 */
            p = stack[top];
            top--;
            printf("%4d\n ", p->score);
            /* 右孩子入栈 */
            if (p->right!= NULL)
            {
                top++;
                stack[top] = p->right;
            }
            /* 左孩子入栈 */
            if (p->left != NULL)
            {
                top++;
                stack[top] = p->left;
            }
        }
        printf("\n");
    }
}
int main()
{
    struct tree *newtree;
    int score1;
    char c;
    score1=0;
    newtree=create_tree();
    printf("二叉树:\n");
    while(1)
    {
        printf("#------------#\n");
        printf("#  I:添加分数\n");
        printf("#  P:打印分数列表\n");
        printf("#  S:查找学生\n");
        printf("#  D:删除学生\n");
        printf("#  E:退出\n");
        printf("#------------#\n");
        printf("请选择输入:");
        scanf("%s",&c);
        switch(c)
        {
            case 'I':
            case 'i':
                inseart_tree(newtree,400);
                inseart_tree(newtree,200);
                inseart_tree(newtree,300);
                inseart_tree(newtree,100);
                inseart_tree(newtree,500);
                inseart_tree(newtree,600);
                break;
            case 'P':
            case 'p':
                printf("打印分数列表:\n");
                traversing_binary_tree(newtree);
                break;
            case 'S':
            case 's':
                printf("请输入要查询的分数:");
                scanf("%d",&score1);
                search(newtree,score1);
                printf("The count is%d\nThe score is%d\n",newtree->count,newtree->root->score);
                break;
            case 'D':
            case 'd':
                printf("请输入要删除的分数:");
                scanf("%d",&score1);
                delete_tree(newtree,score1);
                printf("删除OK！\n");
                break;
            case 'E':
            case 'e':
                exit(0);


        }
    }

}