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

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

            例如輸入:

                 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_面試題集錦

            導航

            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久精品人妻一区二区三区四 | 99久久99久久| 国产成人精品久久二区二区 | 久久国产精品久久| 久久精品国产亚洲av瑜伽| 久久99九九国产免费看小说| 亚洲午夜久久久久久噜噜噜| 久久久久免费看成人影片| 亚洲一区二区三区日本久久九| 性高湖久久久久久久久AAAAA| 久久久久波多野结衣高潮| 国产成人精品久久二区二区| 伊人久久大香线蕉综合5g| 国产亚洲欧美精品久久久| 中文字幕精品久久久久人妻| 亚洲AV日韩AV天堂久久| 人妻精品久久久久中文字幕| 999久久久免费精品国产| 国产精品一区二区久久精品涩爱 | 欧美综合天天夜夜久久| 久久无码高潮喷水| 久久99九九国产免费看小说| 久久国产美女免费观看精品| 久久综合久久综合久久综合| 国产91久久综合| 国产精品免费久久久久电影网| 中文国产成人精品久久不卡| 久久九九久精品国产免费直播| 久久久久久a亚洲欧洲aⅴ | 青春久久| 久久国产成人| 久久艹国产| 国内精品伊人久久久久影院对白| 国内精品久久久久久久97牛牛 | 97精品国产97久久久久久免费 | 漂亮人妻被黑人久久精品| 久久久艹| 久久夜色精品国产亚洲av| 久久精品不卡| 久久一区二区三区免费| 久久露脸国产精品|