• <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>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            求二元查找樹的鏡像

            題目來源: http://blog.163.com/prevBlogPerma.do?host=zhedahht&srl=2541117420072159363370&mode=prev

            題目:輸入一顆二元查找樹,將該樹轉(zhuǎn)換為它的鏡像,即在轉(zhuǎn)換后的二元查找樹中,左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。

            例如輸入:

                 8
                /  \
              6      10
             /\       /\
            5  7    9   11

            輸出:

                  8
                /  \
              10    6
             /\      /\
            11  9  7  5

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

            struct Node {
                
            int value;
                
            struct Node *left;
                
            struct Node *right;
            };

            void
            bst_preorder(
            struct Node *root)
            {
                
            if(root == NULL)
                    
            return;

                printf(
            "%d\t", root->value);
                bst_preorder(root
            ->left);
                bst_preorder(root
            ->right);
            }

            void
            bst_mirror_recursive(
            struct Node *root) /* easy */
            {
                
            if(root == NULL)
                    
            return;

                
            struct Node *ptr = root->left;
                root
            ->left = root->right;
                root
            ->right = ptr;

                bst_mirror_recursive(root
            ->left);
                bst_mirror_recursive(root
            ->right);
            }

            /* STACK : naive */
            #define STACK_SIZE 101
            struct Stack {
                
            void *data[STACK_SIZE];
                
            int top;
            };

            void
            stack_pop(
            struct Stack *stack)
            {
                
            if((stack->top) >= 0)
                    
            --(stack->top);
            }

            void *
            stack_top(
            struct Stack *stack)
            {
                
            if((stack->top) >= 0)
                    
            return stack->data[stack->top];

                
            return NULL;
            }

            void
            stack_push(
            struct Stack *stack, void *entity)
            {
                stack
            ->data[++(stack->top)] = entity;
            }

            int
            stack_isempty(
            struct Stack *stack)
            {
                
            return (stack->top) < 0;
            }

            void
            bst_mirror_nonrecursive(
            struct Node *root, struct Stack *aux_stack) /* stack used : good method */
            {
                stack_push(aux_stack, root);
                
            while(!stack_isempty(aux_stack)) {
                    
            struct Node *node = (struct Node *)stack_top(aux_stack);

                    
            struct Node *ptr = node->left;
                    node
            ->left = node->right;
                    node
            ->right = ptr;

                    stack_pop(aux_stack);
                    
            if(node->left)
                        stack_push(aux_stack, node
            ->left);
                    
            if(node->right)
                        stack_push(aux_stack, node
            ->right);
                }
            }

            int
            main(
            int argc, char **argv)
            {
                
            struct Node a = {5, NULL, NULL};
                
            struct Node b = {7, NULL, NULL};
                
            struct Node c = {9, NULL, NULL};
                
            struct Node d = {11, NULL, NULL};
                
            struct Node e = {6&a, &b};
                
            struct Node f = {10&c, &d};
                
            struct Node g = {8&e, &f};

                bst_preorder(
            &g);
                printf(
            "\n");
                bst_mirror_recursive(
            &g);
                bst_preorder(
            &g);
                printf(
            "\n");

                bst_mirror_recursive(
            &g);
                bst_preorder(
            &g);
                printf(
            "\n");
                
            struct Stack aux = {{0}, -1};
                bst_mirror_nonrecursive(
            &g, &aux);
                bst_preorder(
            &g);
                printf(
            "\n");

                
            return 0;
            }

             




            posted on 2011-06-01 19:58 simplyzhao 閱讀(186) 評論(0)  編輯 收藏 引用 所屬分類: M_面試題集錦

            導(dǎo)航

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            99久久国产综合精品网成人影院 | 久久精品18| 国产一级持黄大片99久久| 亚洲精品高清国产一久久| 久久精品国产99国产精品| 一本色道久久88精品综合| 国产精品99久久久久久猫咪| 久久国产亚洲高清观看| 人人狠狠综合久久亚洲| 久久99国产精品一区二区| 色综合合久久天天给综看| 久久99精品国产麻豆| 久久人人爽人人爽人人片AV不| 日批日出水久久亚洲精品tv| 久久精品国产亚洲AV无码麻豆 | 久久综合中文字幕| 国产欧美久久久精品| 国产精品久久久久免费a∨| 久久影院亚洲一区| 久久国产精品波多野结衣AV| 超级碰久久免费公开视频| 欧美一区二区三区久久综| 免费精品久久久久久中文字幕| 青青草国产精品久久| avtt天堂网久久精品| 无码超乳爆乳中文字幕久久| 亚洲国产另类久久久精品黑人| 四虎影视久久久免费| 成人亚洲欧美久久久久| 日韩欧美亚洲综合久久影院d3| 久久久国产精品亚洲一区| 久久99精品久久只有精品| 久久久久人妻一区精品性色av| 亚洲精品乱码久久久久久中文字幕 | 色欲综合久久躁天天躁| 亚洲国产天堂久久综合| 欧美牲交A欧牲交aⅴ久久| 久久久久久精品无码人妻| 国产一久久香蕉国产线看观看| 中文字幕久久波多野结衣av| 亚洲午夜久久久影院|