青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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菜鳥 閱讀(343) 評論(0)  編輯 收藏 引用 所屬分類: 算法/數據結構
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品v欧美精品v日韩精品| 久久频这里精品99香蕉| 欧美电影在线观看完整版| 亚洲大胆女人| 91久久精品国产91性色tv| 欧美黄色成人网| 亚洲在线视频| 羞羞视频在线观看欧美| 在线日韩av片| 91久久久久久久久| 国产精品久久久亚洲一区| 欧美在线亚洲| 久热精品视频在线观看| 99国产麻豆精品| 亚洲尤物在线视频观看| 狠狠色综合色综合网络| 亚洲片在线观看| 国产精品网站视频| 欧美顶级大胆免费视频| 欧美色欧美亚洲另类七区| 久久av红桃一区二区小说| 久久一区二区三区四区| 亚洲先锋成人| 久久视频一区二区| 亚洲欧美国产一区二区三区| 久久精品国产精品 | 久久精品官网| 一区二区三区免费看| 欧美亚洲视频在线观看| 一区二区激情| 久久全球大尺度高清视频| 亚洲一区二区免费在线| 久久亚洲综合| 午夜视频久久久久久| 老牛国产精品一区的观看方式| 亚洲一区二区三区中文字幕在线| 99这里只有久久精品视频| 一区二区免费在线观看| 亚洲国产婷婷| 久久九九精品| 欧美一区二区三区啪啪| 欧美日产在线观看| 欧美 日韩 国产在线| 国产日韩精品在线| 一本一本久久| 一本色道久久88综合日韩精品| 欧美在线视频日韩| 欧美一区二区日韩一区二区| 欧美日韩国内自拍| 亚洲国产老妈| 在线观看视频一区二区欧美日韩| 亚洲欧美在线aaa| 亚洲午夜精品一区二区| 欧美精品 国产精品| 男女av一区三区二区色多| 国产婷婷色一区二区三区四区 | 午夜视频一区二区| 欧美色道久久88综合亚洲精品| 亚洲高清久久久| 亚洲国产精品久久久久婷婷老年| 久久久久.com| 久久一区免费| 影音先锋亚洲视频| 久久精品亚洲| 美女精品一区| 亚洲欧美激情视频| 国产精品综合不卡av| 亚洲精品久久久久| 亚洲高清一区二| 免播放器亚洲| 亚洲人成高清| 亚洲永久免费观看| 国产精品国产三级国产专区53 | 亚洲欧美日本视频在线观看| 欧美午夜电影网| 在线亚洲美日韩| 欧美在现视频| 伊人久久婷婷| 欧美国产日韩精品| 一区二区成人精品| 欧美一区二区三区日韩视频| 国产亚洲欧美日韩在线一区| 久久精品国产欧美激情| 欧美激情亚洲视频| 亚洲视频一区二区在线观看| 国产精品网站在线播放| 久久九九精品99国产精品| 亚洲第一精品福利| 中日韩美女免费视频网站在线观看| 欧美日韩免费高清| 欧美一级专区免费大片| 欧美激情一区二区三区在线视频观看| 亚洲精品一区二区三区蜜桃久| 欧美日韩在线观看一区二区三区 | 欧美一区二区三区视频在线观看 | 欧美一区在线直播| 亚洲第一精品在线| 欧美先锋影音| 裸体一区二区| 亚洲欧美另类综合偷拍| 欧美国产一区在线| 欧美一区2区视频在线观看| 在线欧美日韩| 国产精品视频免费在线观看| 另类欧美日韩国产在线| 亚洲午夜黄色| 亚洲成在人线av| 欧美一区二区三区视频在线观看| 亚洲一区二区网站| 女人天堂亚洲aⅴ在线观看| 亚洲一区免费看| 亚洲高清久久久| 国产日韩欧美中文在线播放| 欧美精品www在线观看| 久久精品网址| 午夜精品理论片| 亚洲理论在线观看| 欧美成人精品h版在线观看| 欧美一区日韩一区| 一区二区三区四区五区精品视频 | 影音先锋成人资源站| 国产精品久久久久久久午夜片| 蜜桃av一区二区三区| 久久精品72免费观看| 亚洲免费视频观看| 一本久道综合久久精品| 亚洲激情亚洲| 欧美69wwwcom| 老巨人导航500精品| 久久久97精品| 久久精品2019中文字幕| 午夜亚洲精品| 亚洲欧美经典视频| 亚洲线精品一区二区三区八戒| 日韩午夜在线电影| 亚洲精品影视| 亚洲精品人人| 99国产精品| 一区二区高清在线| 一区二区三区免费观看| 一区二区三区视频在线| 夜夜嗨av一区二区三区| 一区二区高清在线| 亚洲素人一区二区| 午夜精品亚洲| 久久爱www.| 久久天堂国产精品| 久久综合成人精品亚洲另类欧美 | 午夜久久99| 欧美一级二区| 久久久久久久成人| 久久亚洲综合| 亚洲电影免费观看高清完整版| 亚洲国产精品免费| 亚洲美女中出| 亚洲一级特黄| 久久国产精品高清| 女生裸体视频一区二区三区| 欧美精品高清视频| 欧美午夜在线一二页| 国产九九精品视频| 在线日韩av| 久久激情五月激情| 久久亚洲精品视频| 欧美日韩成人| 国产欧美在线播放| 亚洲电影网站| 日韩亚洲欧美成人| 午夜精品久久久| 美女视频黄免费的久久| 亚洲精品网站在线播放gif| 亚洲免费一区二区| 久久综合九色综合欧美狠狠| 欧美激情一区二区三区蜜桃视频 | 国内成+人亚洲| 亚洲精品日本| 欧美一区亚洲| 亚洲欧洲精品一区二区| 亚洲免费在线观看| 欧美黑人多人双交| 国产一区二区三区四区三区四| 亚洲国产一区在线| 午夜日韩在线| 亚洲片区在线| 久久www成人_看片免费不卡| 欧美另类在线播放| 在线播放一区| 欧美亚洲一级| 亚洲精品日韩激情在线电影| 欧美在线高清| 国产精品久久久久永久免费观看| 尤物yw午夜国产精品视频明星| 亚洲综合色在线| 欧美黄色精品| 欧美影院视频| 国产精品嫩草99a| 99热这里只有精品8| 牛牛影视久久网| 久久国产夜色精品鲁鲁99| 国产精品高清在线|