• <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>
            posts - 15, comments - 10, trackbacks - 0, articles - 0

            將排序二叉樹轉換成雙向鏈表

            Posted on 2014-01-03 00:41 whspecial 閱讀(3622) 評論(0)  編輯 收藏 引用 所屬分類: 算法&&數據結構
            將排序二叉樹轉化成雙向鏈表,應該是一道很常見的面試題目,網上的實現比較多,有用遞歸也有用中序遍歷法的。看到一位外國友人的實現,還是比較清晰的,思路如下:
            1,如果左子樹不為null,處理左子樹
               1.a)遞歸轉化左子樹為雙向鏈表;
               1.b)找出根結點的前驅節點(是左子樹的最右的節點)
               1.c)將上一步找出的節點和根結點連接起來
            2,如果右子樹不為null,處理右子樹(和上面的很類似)
               1.a)遞歸轉化右子樹為雙向鏈表;
               1.b)找出根結點的后繼節點(是右子樹的最左的節點)
               1.c)將上一步找出的節點和根結點連接起來
            3,找到最左邊的節點并返回

            附上國外友人的鏈接:http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/

            下面是代碼實現:
            bintree2listUtil函數返回的node* 是root節點,bintree2list函數返回的是頭節點
            This is the core function to convert Tree to list. This function follows
              steps 1 and 2 of the above algorithm */
            node* bintree2listUtil(node* root)
            {
                // Base case
                if (root == NULL)
                    return root;
             
                // Convert the left subtree and link to root
                if (root->left != NULL)
                {
                    // Convert the left subtree
                    node* left = bintree2listUtil(root->left);
             
                    // Find inorder predecessor. After this loop, left
                    // will point to the inorder predecessor
                    for (; left->right!=NULL; left=left->right);
             
                    // Make root as next of the predecessor
                    left->right = root;
             
                    // Make predecssor as previous of root
                    root->left = left;
                }
             
                // Convert the right subtree and link to root
                if (root->right!=NULL)
                {
                    // Convert the right subtree
                    node* right = bintree2listUtil(root->right);
             
                    // Find inorder successor. After this loop, right
                    // will point to the inorder successor
                    for (; right->left!=NULL; right = right->left);
             
                    // Make root as previous of successor
                    right->left = root;
             
                    // Make successor as next of root
                    root->right = right;
                }
             
                return root;
            }
             
            // The main function that first calls bintree2listUtil(), then follows step 3
            //  of the above algorithm
            node* bintree2list(node *root)
            {
                // Base case
                if (root == NULL)
                    return root;
             
                // Convert to DLL using bintree2listUtil()
                root = bintree2listUtil(root);
             
                // bintree2listUtil() returns root node of the converted
                // DLL.  We need pointer to the leftmost node which is
                // head of the constructed DLL, so move to the leftmost node
                while (root->left != NULL)
                    root = root->left;
             
                return (root);
            亚洲精品99久久久久中文字幕| 久久国产影院| 精品久久久久久中文字幕| 97久久国产亚洲精品超碰热| 精品久久一区二区| 久久一区二区三区99| 日韩人妻无码一区二区三区久久 | 国产成人久久精品一区二区三区 | 久久妇女高潮几次MBA| 久久精品国产亚洲AV高清热| 99国内精品久久久久久久| 中文字幕久久亚洲一区| 精品无码久久久久国产| 亚洲国产日韩欧美综合久久| 99久久人妻无码精品系列| 无码精品久久一区二区三区| 好久久免费视频高清| 中文字幕久久波多野结衣av| 欧美久久综合性欧美| 久久人与动人物a级毛片| 久久99精品久久久久久hb无码 | 四虎影视久久久免费观看| 久久99国产综合精品| 久久精品国产精品青草app| 国内精品久久久久久99蜜桃 | 久久精品中文无码资源站| 99re久久精品国产首页2020| 91久久精一区二区三区大全| 无码8090精品久久一区 | 熟妇人妻久久中文字幕| 东京热TOKYO综合久久精品 | 亚洲?V乱码久久精品蜜桃 | 久久99精品国产一区二区三区| 久久国产高潮流白浆免费观看| 亚洲精品综合久久| 久久久WWW成人免费毛片| 伊人丁香狠狠色综合久久| 99久久婷婷国产综合亚洲| 国产69精品久久久久777| 91精品国产高清91久久久久久| 久久久久无码精品国产|