久久亚洲日韩精品一区二区三区 ,精品国产乱码久久久久久人妻,久久免费视频6

將排序二叉樹(shù)轉(zhuǎn)換成雙向鏈表

Posted on 2014-01-03 00:41 whspecial 閱讀(3621) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): 算法&&數(shù)據(jù)結(jié)構(gòu)

將排序二叉樹(shù)轉(zhuǎn)化成雙向鏈表，應(yīng)該是一道很常見(jiàn)的面試題目，網(wǎng)上的實(shí)現(xiàn)比較多，有用遞歸也有用中序遍歷法的。看到一位外國(guó)友人的實(shí)現(xiàn)，還是比較清晰的，思路如下：

1，如果左子樹(shù)不為null，處理左子樹(shù)

1.a）遞歸轉(zhuǎn)化左子樹(shù)為雙向鏈表；

1.b）找出根結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)（是左子樹(shù)的最右的節(jié)點(diǎn)）

1.c）將上一步找出的節(jié)點(diǎn)和根結(jié)點(diǎn)連接起來(lái)

2，如果右子樹(shù)不為null，處理右子樹(shù)（和上面的很類(lèi)似）

1.a）遞歸轉(zhuǎn)化右子樹(shù)為雙向鏈表；

1.b）找出根結(jié)點(diǎn)的后繼節(jié)點(diǎn)（是右子樹(shù)的最左的節(jié)點(diǎn)）

1.c）將上一步找出的節(jié)點(diǎn)和根結(jié)點(diǎn)連接起來(lái)

3，找到最左邊的節(jié)點(diǎn)并返回

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

下面是代碼實(shí)現(xiàn)：

bintree2listUtil函數(shù)返回的node＊是root節(jié)點(diǎn)，bintree2list函數(shù)返回的是頭節(jié)點(diǎn)

 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);

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

實(shí)驗(yàn)室宅男的一畝三分地

導(dǎo)航

常用鏈接

留言簿

隨筆分類(lèi)

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

將排序二叉樹(shù)轉(zhuǎn)換成雙向鏈表