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

            堅信:勤能補拙

            把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

            題目出處: http://zhedahht.blog.163.com/

            題目:輸入一棵二元查找樹,將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點,只調(diào)整指針的指向。

              比如將二元查找樹
               
                                                    10
                                                      /    \
                                                    6       14
                                                  /  \     /  \
                                                4     8  12    16
            轉(zhuǎn)換成雙向鏈表

            4=6=8=10=12=14=16


            思路:遞歸,在一時找不到遞歸的靈感的時候,多考慮考慮遞歸的參數(shù),有時更重要的是考慮遞歸的返回值
                  每處理一個節(jié)點,首先獲取左子樹和右子樹所返回的鏈表,然后拼接

            代碼:
            #include<stdio.h>
            #include
            <string.h>
            #include
            <stdlib.h>

            /* Problem: Convert a binary search tree into a sorted linkedlist */
            /* When it comes to Tree-Structure, recursion is always the most common solution.
               When designing recursion solution, should consider:
                   1. the parameters
                   2(important). the return object
            */

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

            struct Node *
            BTree2List(
            struct Node *root)
            {
                
            if(root == NULL)
                    
            return NULL;
                
            struct Node *ret = NULL;

                
            /* Convert the left tree into a sorted linkedlist */
                
            struct Node *l_linkedlist = BTree2List(root->left);
                ret 
            = l_linkedlist==NULL ? root : l_linkedlist;

                
            /* Convert the right tree into a sorted linkedlist */
                
            struct Node *r_linkedlist = BTree2List(root->right);
                
            while(l_linkedlist && l_linkedlist->right)
                    l_linkedlist 
            = l_linkedlist->right;

                
            /* Combine */
                
            if(l_linkedlist)
                    l_linkedlist
            ->right = root;
                root
            ->left = l_linkedlist;
                root
            ->right = r_linkedlist;
                
            if(r_linkedlist)
                    r_linkedlist
            ->left = root;
                
                
            return ret;
            }

            int main(int argc, char** argv)
            {
                
            struct Node a = {4, NULL, NULL};
                
            struct Node b = {8, NULL, NULL};
                
            struct Node c = {12, NULL, NULL};
                
            struct Node d = {16, NULL, NULL};
                
            struct Node e = {6, NULL, &b};
                
            struct Node f = {14&c, NULL};
                
            struct Node g = {10&e, &f};

                
            struct Node *ret = BTree2List(&g);
                
            while(ret && ret->right) {
                    ret 
            = ret->right;
                }

                
            while(ret) {
                    printf(
            "%d\n", ret->value);
                    ret 
            = ret->left;
                }

                
            return 0;
            }


            posted on 2011-05-23 09:09 simplyzhao 閱讀(381) 評論(0)  編輯 收藏 引用 所屬分類: M_面試題集錦

            導(dǎo)航

            <2011年5月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            日产精品久久久久久久| 久久男人Av资源网站无码软件 | 久久免费看黄a级毛片| 久久婷婷五月综合色奶水99啪| 久久久久久免费视频| 亚洲欧美日韩久久精品第一区| 久久久国产精品福利免费| 日本亚洲色大成网站WWW久久| 午夜精品久久久久久99热| 999久久久国产精品| 久久强奷乱码老熟女网站| 99久久国产主播综合精品| 亚洲精品午夜国产VA久久成人 | 久久婷婷五月综合色奶水99啪| 久久99热狠狠色精品一区| 一本综合久久国产二区| a高清免费毛片久久| 久久AV高潮AV无码AV| 国产精品久久久久乳精品爆| 精品国产VA久久久久久久冰 | 国产精品久久久久AV福利动漫| 久久伊人精品青青草原日本| 久久亚洲欧美日本精品| 亚洲精品乱码久久久久66| 日韩AV毛片精品久久久| 91久久精品国产成人久久| 国产99久久精品一区二区| 人人狠狠综合久久88成人| 狠狠综合久久综合88亚洲| 一本大道久久香蕉成人网| 国产成人久久久精品二区三区| 69SEX久久精品国产麻豆| 久久综合给合久久狠狠狠97色| 亚洲?V乱码久久精品蜜桃 | 久久精品国产91久久麻豆自制| 日韩久久久久久中文人妻| 久久人人爽人人人人爽AV| 久久久高清免费视频| 久久国内免费视频| 狠狠色婷婷久久综合频道日韩 | 欧美久久天天综合香蕉伊|