• <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);
            97精品伊人久久久大香线蕉 | 99久久夜色精品国产网站| 久久精品国产只有精品2020| 国产一区二区精品久久| 国产精品无码久久久久| 久久精品国产男包| 九九久久99综合一区二区| 久久人搡人人玩人妻精品首页 | 久久SE精品一区二区| 国产69精品久久久久久人妻精品| 伊人久久精品无码二区麻豆| 国内精品久久人妻互换| 国产精品午夜久久| 久久成人国产精品| 色综合久久天天综线观看| 99久久精品费精品国产一区二区| 久久99亚洲综合精品首页| 久久青青草原亚洲av无码app| 麻豆精品久久精品色综合| 色综合久久久久无码专区| 欧美亚洲日本久久精品| 久久国产精品-国产精品| 久久午夜无码鲁丝片午夜精品| 97精品国产91久久久久久| 国内精品伊人久久久久777| 国产毛片久久久久久国产毛片| 狠狠色婷婷久久一区二区三区| 亚洲精品国精品久久99热 | 久久亚洲天堂| 国产精品美女久久久网AV| 精品久久久噜噜噜久久久| 亚洲精品国产美女久久久| 久久噜噜久久久精品66| 久久精品国产亚洲7777| 99久久婷婷国产一区二区| 青青草原综合久久大伊人精品| 日日噜噜夜夜狠狠久久丁香五月 | 亚洲熟妇无码另类久久久| 久久婷婷五月综合色奶水99啪| 久久免费视频一区| 噜噜噜色噜噜噜久久|