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

            Where there is a dream ,there is hope

              C++博客 :: 首頁(yè) :: 聯(lián)系 :: 聚合  :: 管理
              64 Posts :: 0 Stories :: 8 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(1)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            原文地址:http://zhedahht.blog.163.com/blog/static/254111742007127104759245/
            題目:輸入一棵二元查找樹(shù),將該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn),只調(diào)整指針的指向。

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

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

              分析:本題是微軟的面試題。很多與樹(shù)相關(guān)的題目都是用遞歸的思路來(lái)解決,本題也不例外。下面我們用兩種不同的遞歸思路來(lái)分析。

              思路一:當(dāng)我們到達(dá)某一結(jié)點(diǎn)準(zhǔn)備調(diào)整以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹(shù)時(shí),先調(diào)整其左子樹(shù)將左子樹(shù)轉(zhuǎn)換成一個(gè)排好序的左子鏈表,再調(diào)整其右子樹(shù)轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點(diǎn)(左子樹(shù)的最大結(jié)點(diǎn))、當(dāng)前結(jié)點(diǎn)和右子鏈表的最左結(jié)點(diǎn)(右子樹(shù)的最小結(jié)點(diǎn))。從樹(shù)的根結(jié)點(diǎn)開(kāi)始遞歸調(diào)整所有結(jié)點(diǎn)。

              思路二:我們可以中序遍歷整棵樹(shù)。按照這個(gè)方式遍歷樹(shù),比較小的結(jié)點(diǎn)先訪問(wèn)。如果我們每訪問(wèn)一個(gè)結(jié)點(diǎn),假設(shè)之前訪問(wèn)過(guò)的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表,我們?cè)侔颜{(diào)整當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪問(wèn)過(guò)之后,整棵樹(shù)也就轉(zhuǎn)換成一個(gè)排序雙向鏈表了。

            參考代碼:

            首先我們定義二元查找樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下:
                struct BSTreeNode // a node in the binary search tree
                {
                    int          m_nValue; // value of node
                    BSTreeNode  *m_pLeft;  // left child of node
                    BSTreeNode  *m_pRight; // right child of node
                };

            思路一對(duì)應(yīng)的代碼:
            ///////////////////////////////////////////////////////////////////////
            // Covert a sub binary-search-tree into a sorted double-linked list
            // Input: pNode - the head of the sub tree
            //        asRight - whether pNode is the right child of its parent
            // Output: if asRight is true, return the least node in the sub-tree
            //         else return the greatest node in the sub-tree
            ///////////////////////////////////////////////////////////////////////
            BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
            {
                  if(!pNode)
                        return NULL;

                  BSTreeNode *pLeft = NULL;
                  BSTreeNode *pRight = NULL;

                  // Convert the left sub-tree
                  if(pNode->m_pLeft)
                        pLeft = ConvertNode(pNode->m_pLeft, false);

                  // Connect the greatest node in the left sub-tree to the current node
                  if(pLeft)
                  {
                        pLeft->m_pRight = pNode;
                        pNode->m_pLeft = pLeft;
                  }

                  // Convert the right sub-tree
                  if(pNode->m_pRight)
                        pRight = ConvertNode(pNode->m_pRight, true);

                  // Connect the least node in the right sub-tree to the current node
                  if(pRight)
                  {
                        pNode->m_pRight = pRight;
                        pRight->m_pLeft = pNode;
                  }

                  BSTreeNode *pTemp = pNode;

                  // If the current node is the right child of its parent, 
                  // return the least node in the tree whose root is the current node
                  if(asRight)
                  {
                        while(pTemp->m_pLeft)
                              pTemp = pTemp->m_pLeft;
                  }
                  // If the current node is the left child of its parent, 
                  // return the greatest node in the tree whose root is the current node
                  else
                  {
                        while(pTemp->m_pRight)
                              pTemp = pTemp->m_pRight;
                  }
             
                  return pTemp;
            }

            ///////////////////////////////////////////////////////////////////////
            // Covert a binary search tree into a sorted double-linked list
            // Input: the head of tree
            // Output: the head of sorted double-linked list
            ///////////////////////////////////////////////////////////////////////
            BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
            {
                  // As we want to return the head of the sorted double-linked list,
                  // we set the second parameter to be true
                  return ConvertNode(pHeadOfTree, true);
            }

            思路二對(duì)應(yīng)的代碼:
            ///////////////////////////////////////////////////////////////////////
            // Covert a sub binary-search-tree into a sorted double-linked list
            // Input: pNode -           the head of the sub tree
            //        pLastNodeInList - the tail of the double-linked list
            ///////////////////////////////////////////////////////////////////////
            void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
            {
                  if(pNode == NULL)
                        return;

                  BSTreeNode *pCurrent = pNode;

                  // Convert the left sub-tree
                  if (pCurrent->m_pLeft != NULL)
                        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

                  // Put the current node into the double-linked list
                  pCurrent->m_pLeft = pLastNodeInList; 
                  if(pLastNodeInList != NULL)
                        pLastNodeInList->m_pRight = pCurrent;

                  pLastNodeInList = pCurrent;

                  // Convert the right sub-tree
                  if (pCurrent->m_pRight != NULL)
                        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
            }

            ///////////////////////////////////////////////////////////////////////
            // Covert a binary search tree into a sorted double-linked list
            // Input: pHeadOfTree - the head of tree
            // Output: the head of sorted double-linked list
            ///////////////////////////////////////////////////////////////////////
            BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
            {
                  BSTreeNode *pLastNodeInList = NULL;
                  ConvertNode(pHeadOfTree, pLastNodeInList);

                  // Get the head of the double-linked list
                  BSTreeNode *pHeadOfList = pLastNodeInList;
                  while(pHeadOfList && pHeadOfList->m_pLeft)
                        pHeadOfList = pHeadOfList->m_pLeft;

                  return pHeadOfList;
            }

            posted on 2010-12-17 08:58 IT菜鳥 閱讀(337) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法/數(shù)據(jù)結(jié)構(gòu)

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            一级a性色生活片久久无少妇一级婬片免费放| 午夜精品久久久久久久| 久久99国产精品久久久| 久久久久久毛片免费播放| 丁香五月网久久综合| 久久久久国产精品麻豆AR影院| 久久久久久久久久久免费精品 | 超级碰久久免费公开视频| 国产成人99久久亚洲综合精品| 日韩电影久久久被窝网| 久久综合88熟人妻| 久久国产香蕉视频| 久久久久女人精品毛片| 久久国产香蕉一区精品| 国内精品久久久久久久97牛牛| 99久久精品无码一区二区毛片| 久久午夜福利无码1000合集| 国产亚洲精品美女久久久| 97久久精品人人做人人爽| 亚洲精品蜜桃久久久久久| 久久国产香蕉视频| 青青草原1769久久免费播放| 久久综合九色综合网站| 国产免费久久精品丫丫| 久久99精品久久只有精品| 久久亚洲sm情趣捆绑调教| 亚洲国产精品久久久久婷婷软件 | 伊人久久大香线焦AV综合影院| 久久精品国产影库免费看| 99久久国产宗和精品1上映 | 九九久久99综合一区二区| 国产成人精品综合久久久久| 欧美久久亚洲精品| 国内精品伊人久久久久影院对白| 97久久天天综合色天天综合色hd| 久久久亚洲裙底偷窥综合| 久久综合精品国产一区二区三区| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 久久人人爽人人爽人人片AV东京热 | 久久综合狠狠综合久久| 人妻丰满AV无码久久不卡 |