• <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++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              64 Posts :: 0 Stories :: 8 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(1)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            原文地址:http://zhedahht.blog.163.com/blog/static/254111742007127104759245/
            題目:輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點,只調整指針的指向。

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

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

              分析:本題是微軟的面試題。很多與樹相關的題目都是用遞歸的思路來解決,本題也不例外。下面我們用兩種不同的遞歸思路來分析。

              思路一:當我們到達某一結點準備調整以該結點為根結點的子樹時,先調整其左子樹將左子樹轉換成一個排好序的左子鏈表,再調整其右子樹轉換右子鏈表。最近鏈接左子鏈表的最右結點(左子樹的最大結點)、當前結點和右子鏈表的最左結點(右子樹的最小結點)。從樹的根結點開始遞歸調整所有結點。

              思路二:我們可以中序遍歷整棵樹。按照這個方式遍歷樹,比較小的結點先訪問。如果我們每訪問一個結點,假設之前訪問過的結點已經調整成一個排序雙向鏈表,我們再把調整當前結點的指針將其鏈接到鏈表的末尾。當所有結點都訪問過之后,整棵樹也就轉換成一個排序雙向鏈表了。

            參考代碼:

            首先我們定義二元查找樹結點的數據結構如下:
                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
                };

            思路一對應的代碼:
            ///////////////////////////////////////////////////////////////////////
            // 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);
            }

            思路二對應的代碼:
            ///////////////////////////////////////////////////////////////////////
            // 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菜鳥 閱讀(333) 評論(0)  編輯 收藏 引用 所屬分類: 算法/數據結構
            久久有码中文字幕| 99久久免费国产精品热| 国内精品免费久久影院| 久久91精品综合国产首页| 久久久久久久亚洲精品| 久久亚洲日韩看片无码| 久久精品国产99国产电影网| 久久天天日天天操综合伊人av| 少妇熟女久久综合网色欲| 久久久久综合网久久| 久久受www免费人成_看片中文| 精品久久人妻av中文字幕| 久久久久亚洲AV无码去区首| 欧美一区二区三区久久综| 久久综合亚洲色HEZYO国产| 国产美女久久久| 伊人久久无码中文字幕| 色99久久久久高潮综合影院| 久久久久国产精品| 国产成人精品白浆久久69| 久久这里只有精品首页| 久久精品国产亚洲Aⅴ香蕉 | 日韩久久久久久中文人妻| 精品久久久久久99人妻| 久久这里只有精品久久| 99久久精品国产高清一区二区| 国产aⅴ激情无码久久| 国产99久久久国产精品小说| 久久精品国产精品亚洲| 精品久久久无码中文字幕| 日本道色综合久久影院| 精品久久无码中文字幕| 国产99精品久久| 狠狠色噜噜狠狠狠狠狠色综合久久| 精品久久久无码人妻中文字幕豆芽| 97精品依人久久久大香线蕉97 | 久久久久亚洲AV成人网人人网站 | 性做久久久久久久久| 久久综合色之久久综合| 亚洲精品乱码久久久久久不卡| 国产激情久久久久影院老熟女免费|