• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Just enjoy programming

            二叉查找樹實現

            #include<stdio.h>
            #include<stdlib.h>
            #include<string.h>

            /*結構體節點*/
            typedef struct  _node{
                int key;
                struct _node *left;
                struct _node *right;
                struct _node *parent;
            }node;


            /*插入節點*/
            void insert(node *root,node *toInsert)
            {
                node *p,*q;
                p=root;
                q=NULL;
                if(toInsert==NULL || root==NULL)
                {
                    return;
                }

                while(p!=NULL)
                {
                    q=p;/*記錄父節點*/
                    if(toInsert->key<p->key)
                    {
                        p=p->left;
                    }else{
                        p=p->right;
                    }    
                }
                if(toInsert->key<q->key)
                {
                    q->left=toInsert;
                }else{
                    q->right=toInsert;
                }
                toInsert->parent=q;
                toInsert->left=NULL;
                toInsert->right=NULL;
            }

            /*遞歸中序遍歷根節點*/
            void middleSearch(node *root)
            {
                if(root!=NULL)
                {
                    middleSearch(root->left);
                    printf("%d\t",root->key);
                    middleSearch(root->right);
                }
            }
            /*先序遍歷*/
            void preSearch(node *root)
            {
                if(root!=NULL)
                {
                    printf("%d\t",root->key);
                    preSearch(root->left);
                    preSearch(root->right);
                }
            }

            /*查找返回節點關鍵字為key的節點*/
            node* search(node *root,int key)
            {
                node *p=root;
                while(p!=NULL)
                {
                    if(key<p->key)
                    {
                        p=p->left;
                    }else if(key>p->key)
                    {
                        p=p->right;
                    }else
                        break;
                }
                return p;
            }

            /*查找二叉樹最小值*/
            node *minimun(node *root)
            {
                node *p=root;
                if(p==NULL)
                    return p;
                while(p->left!=NULL)
                    p=p->left;
                printf("min %d\n",p->key);
                return p;
            }

            /*查找二叉樹最大值*/
            node *maximun(node *root)
            {
                node *p=root;
                if(p==NULL)
                    return;
                while(p->right!=NULL)
                    p=p->right;
                printf("max %d\n",p->key);
                return p;
            }
            /*找節點后續*/
            node* successor(node *x)
            {
                node *p;
                if(NULL==x)
                    return x;
                if(x->right!=NULL)
                    return minimun(x->right);
                p=x->parent;
                while(p!=NULL && p->right==x)
                {
                    x=p;
                    p=p->parent;
                }
                return p;
            }

            /*刪除節點*/
            void delete(node *root,node *toDelete)
            {
                node *p,*q;
                int key;
                if(root==NULL || toDelete==NULL)
                    return ;
                p=toDelete->parent;

                /*第一種情況,要刪除的節點的左右子樹都為空*/
                if(toDelete->left ==NULL && toDelete->right ==NULL)
                {
                    if(p==NULL)/*要刪除的是根節點*/
                    {
                        free(toDelete);
                        return;
                    }
                    if(p->left==toDelete)
                    {
                        p->left=NULL;
                    }else
                        p->right=NULL;
                    free(toDelete);

                }

                /*第二種情況,要刪除的左子樹為空,右子樹不為空*/
                else if(toDelete->left==NULL)
                {    
                    if(p==NULL)
                    {
                        q=root->right;
                        root->key=q->key;
                        root->left=q->left;
                        root->right=q->right;

                        free(q);
                        return;
                    }
                    else if(p->left==toDelete)
                    {
                        p->left=toDelete->right;
                    }else
                        p->right=toDelete->right;
                    toDelete->right->parent=p;
                    free(toDelete);
                }

                /* 第三種情況,要刪除的右子樹為空,左子樹不為空*/
                else if(toDelete->right==NULL)
                {
                    if(p==NULL)
                    {
                        q=root->left;
                        root->key=q->key;
                        root->left=q->left;
                        root->right=q->right;
                        root->parent=NULL;
                        free(q);
                        return;
                    }
                    else if(p->left==toDelete)
                    {
                        p->left=toDelete->left;
                    }else
                        p->right=toDelete->right;
                    toDelete->parent=p;
                    free(toDelete);
                }

                /* 第四種情況,要刪除的左右子樹都不為空*/
                else{
                        q=successor(toDelete);
                        key=q->key;
                        delete(root,q);
                        toDelete->key=key;
                }
            }

            int main()
            {
                node *root;

                int a[12]={15,5,3,12,10,13,6,7,16,20,18,23};
                node *toInsert;
                node *x,*y;
                int i;
                /*創建頭節點*/
                if((root=(node*)malloc(sizeof(node)))==NULL)
                {
                    perror("malloc error");
                    exit(1);
                }
                root->key=a[0];
                /*插入節點*/
                for(i=1;i<12;i++)
                {
                    if((toInsert=(node*)malloc(sizeof(node)))==NULL)
                    {
                        perror("malloc error");
                        exit(1);
                    }
                    toInsert->key=a[i];
                    insert(root,toInsert);
                }

                /*中序遍歷*/
                middleSearch(root);
                printf("\n");
                /*先序遍歷*/
                preSearch(root);
                printf("\n");

                /*最大值*/
                maximun(root);
                /*最小值*/
                minimun(root);

                /*查找關鍵字節點及其前驅*/
                x=search(root,6);
                y=successor(x);
                if(y!=NULL)
                    printf("節點 6 后驅 %d\n",y->key);

                x=search(root,3);
                y=successor(x);
                if(y!=NULL)
                    printf("節點 3 后驅 %d\n",y->key);


                x=search(root,13);
                y=successor(x);
                if(y!=NULL)
                    printf("節點 13 后驅 %d\n",y->key);


                x=search(root,23);
                y=successor(x);
                if(y!=NULL)
                    printf("節點 23 后驅 %d\n",y->key);

                /*刪除節點*/
                printf("before delete the node\n");
                x=search(root,13);

                delete(root,x);
                printf("\nafter delete the node\n");
                
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);

                if((toInsert=(node*)malloc(sizeof(node)))==NULL)
                {
                    perror("malloc error");
                    exit(1);
                }
                toInsert->key=13;
                insert(root,toInsert);
                printf("\n中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);


                printf("\nbefore delete the node\n");
                x=search(root,16);
                delete(root,x);
                printf("\nafter delete the node\n");
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);

                if((toInsert=(node*)malloc(sizeof(node)))==NULL)
                {
                    perror("malloc error");
                    exit(1);
                }
                toInsert->key=16;
                insert(root,toInsert);
                printf("\n中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);

                printf("\nbefore delete the node\n");
                x=search(root,5);
                delete(root,x);
                printf("\nafter delete the node\n");
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);
                if((toInsert=(node*)malloc(sizeof(node)))==NULL)
                {
                    perror("malloc error");
                    exit(1);
                }
                toInsert->key=5;
                insert(root,toInsert);

                printf("\n中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);

                printf("\nbefore delete the node\n");
                x=search(root,15);

                delete(root,x);
                printf("\nafter delete the node\n");
               
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);

                printf("\n");


                printf("before delete the node\n");
                x=search(root,16);

                delete(root,x);
                printf("\nafter delete the node\n");
               
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);
                printf("\n");



                printf("before delete the node\n");
                x=search(root,18);

                delete(root,x);
                printf("\nafter delete the node\n");
               
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);
                printf("\n");

                printf("before delete the node\n");
                x=search(root,20);

                delete(root,x);
                printf("\nafter delete the node\n");
               
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);
                printf("\n");


                printf("before delete the node\n");
                x=search(root,23);

                delete(root,x);
                printf("\nafter delete the node\n");
               
                printf("中序遍歷\n");
                middleSearch(root);
                printf("\n先序遍歷\n");
                preSearch(root);
                printf("\n");
            }
             

            posted on 2011-03-28 16:15 周強 閱讀(296) 評論(0)  編輯 收藏 引用 所屬分類: 算法

            日韩一区二区久久久久久| 久久人人爽人人澡人人高潮AV| 久久久久亚洲AV综合波多野结衣 | 精品久久久久国产免费| A级毛片无码久久精品免费| 久久精品成人免费国产片小草| 国内精品久久久久影院老司| 狠狠色婷婷久久一区二区| 国产精品久久久久久影院 | 久久强奷乱码老熟女网站| 国产精品一区二区久久精品涩爱 | 久久精品亚洲福利| 亚洲日韩欧美一区久久久久我| 久久久一本精品99久久精品66| 国产精品欧美亚洲韩国日本久久 | 国产成人精品久久综合| 香蕉久久夜色精品国产2020| 久久er国产精品免费观看2| 日韩影院久久| 91久久香蕉国产熟女线看| 精品久久久久久久久免费影院| 久久精品国产一区| 无码专区久久综合久中文字幕| 国产午夜精品理论片久久 | 9191精品国产免费久久| 久久这里只有精品18| 久久夜色撩人精品国产小说| 成人国内精品久久久久一区| 国产精品99久久久精品无码 | 久久无码国产| 四虎国产精品免费久久5151| 一本久道久久综合狠狠躁AV| 一本色道久久88加勒比—综合| 久久99精品久久久久子伦| 色婷婷综合久久久中文字幕| 无码人妻久久一区二区三区蜜桃| 久久久久噜噜噜亚洲熟女综合 | 99精品久久精品一区二区| 久久精品免费全国观看国产| 久久伊人五月天论坛| 日本国产精品久久|