c語言二叉樹--實作

/*系統環境：centos 5.8

 *

 */

#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;

        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;

                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)

            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;

    while((p!=NULL)&&(!flag2))

            flag2=1;

        else if(p->score>score)

            f=p;

    if(flag2)

        if((p->left==NULL)||(p->right==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;

                f->right=s;

        free(p);

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

/*周遊二叉樹*/

void traversing_binary_tree( struct tree *t)

    struct node *stack[MAXSIZE], *p;

    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)

                stack[top] = p->left;

        printf("\n");

int main()

    struct tree *newtree;

    int score1;

    char c;

    score1=0;

    newtree=create_tree();

    printf("二叉樹:\n");

        printf("#------------#\n");

        printf("#  I:添加分數\n");

        printf("#  P:列印分數清單\n");

        printf("#  S:查找學生\n");

        printf("#  D:删除學生\n");

        printf("#  E:退出\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);

            case 'P':

            case 'p':

                printf("列印分數清單:\n");

                traversing_binary_tree(newtree);

            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);

            case 'D':

            case 'd':

                printf("請輸入要删除的分數:");

                delete_tree(newtree,score1);

                printf("删除OK！\n");

            case 'E':

            case 'e':

                exit(0);