劍指offer之二叉搜索樹和雙向鏈表

1 問題

比如我們搜索二叉樹如下，我們需要變成雙向鏈表
 

 

 
2 分析

我們知道這個(gè)變成雙向鏈接的時(shí)候是按照樹的中序遍歷打印的，我們只需要在中序遍歷打印的時(shí)候操作該節(jié)點(diǎn)，我們可以用臨時(shí)變量保存這個(gè)節(jié)點(diǎn)，同時(shí)我們也需要單獨(dú)增加一個(gè)鏈表節(jié)點(diǎn)變量，我們需要保證這個(gè)節(jié)點(diǎn)的左邊指向是該鏈表節(jié)點(diǎn)，然后該鏈表節(jié)點(diǎn)的右指向是這個(gè)節(jié)點(diǎn)，然后我們?cè)侔堰@個(gè)節(jié)點(diǎn)賦值給這個(gè)鏈表節(jié)點(diǎn)，就這樣一直移動(dòng)下去即可。

 

 
3 代碼實(shí)現(xiàn)

我這里以下面的搜索二叉樹進(jìn)行操作的

     
                    4
               2         6
            1     3   5     7     

    #include <stdio.h>
    #include <stdlib.h>
     
    typedef struct Tree
    {
        int value;
        struct Tree* left;
        struct Tree* right;
    } Tree;
     
    /*
     * 把搜索二叉樹轉(zhuǎn)成雙向鏈表，我們按照中序遍歷
     */
    void convertNode(Tree* node, Tree** lastNodeList)
    {
        if (node == NULL)
            return;
        Tree* pCurrent = node;
        if (pCurrent->left != NULL)
        {
            convertNode(pCurrent->left, lastNodeList);
        }
        //這里就要進(jìn)行我們每個(gè)節(jié)點(diǎn)的前后正確的指向了
        pCurrent->left = *lastNodeList;
        if (*lastNodeList != NULL)
        {
            (*lastNodeList)->right = pCurrent;
        }
        *lastNodeList = pCurrent;
     
        if (pCurrent->right != NULL)
        {
            convertNode(pCurrent->right, lastNodeList);
        }
    }
    
     
    /*
     * 把翻轉(zhuǎn)好的雙向鏈表尾巴節(jié)點(diǎn)移動(dòng)到鏈表頭
     */
    Tree* convert(Tree* node, Tree* lastNodeList)
    {
        if (node == NULL || lastNodeList == NULL)
        {
            printf("node is NULL or lastNodeList is NULL\n");
            return NULL;
        }
        Tree* last = NULL;
        convertNode(node, &lastNodeList);
        //因?yàn)檫@個(gè)時(shí)候lastNodeList已經(jīng)到了雙向鏈表尾巴，我們需要移動(dòng)到鏈表頭
        Tree* headNodeList = lastNodeList;
        while (headNodeList != NULL && headNodeList->left != NULL)
        {
            headNodeList = headNodeList -> left;
        }
        return headNodeList;
    }
     
    /*
     * 雙向鏈表從左到右打印
     */
    void printRightList(Tree* headNodeList)
    {
        if (headNodeList == NULL)
        {
            printf("headNodeList is NULL\n");
            return;
        }
        printf("we will print list from left to right\n");
        Tree* pCurrent = headNodeList;
        while (pCurrent != NULL)
        {
            printf("value is %d\n", pCurrent->value);
            pCurrent = pCurrent->right;
        }
    }
     
    /*
     * 雙向鏈表從右到左打印
     */
    void printLeftList(Tree* headNodeList)
    {
        if (headNodeList == NULL)
        {
            printf("headNodeList is NULL\n");
            return;
        }
        printf("we will print list from right to left\n");
        Tree* pCurrent = headNodeList;
        //先把鏈表頭結(jié)點(diǎn)移動(dòng)為鏈表的尾巴
        while (pCurrent->right != NULL)
        {
            //printf("value is %d\n", pCurrent->value);
            pCurrent = pCurrent->right;
        }
        //pCurrent = pCurrent->left;
        
        while (pCurrent != NULL)
        {
            printf("value is %d\n", pCurrent->value);
            pCurrent = pCurrent->left;
        }
    }
     
     
    int main(void)
    {
        Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7;
        node1 = (Tree *)malloc(sizeof(Tree));
        node2 = (Tree *)malloc(sizeof(Tree));
        node3 = (Tree *)malloc(sizeof(Tree));
        node4 = (Tree *)malloc(sizeof(Tree));
        node5 = (Tree *)malloc(sizeof(Tree));
        node6 = (Tree *)malloc(sizeof(Tree));
        node7 = (Tree *)malloc(sizeof(Tree));
        node1->value = 4;
        node2->value = 2;
        node3->value = 6;
        node4->value = 1;
        node5->value = 3;
        node6->value = 5;
        node7->value = 7;
        
        node1->left = node2;
        node1->right = node3;
        node2->left = node4;
        node2->right = node5;
        node3->left = node6;
        node3->right = node7;
        
        node4->left = NULL;
        node4->right = NULL;
        
        node5->left = NULL;
        node5->right = NULL;
     
        node6->left = NULL;
        node6->right = NULL;
        
        node7->left = NULL;
        node7->right = NULL;
        
        Tree* list = (Tree *)malloc(sizeof(Tree));
        if (!list)
        {
            printf("malloc list fail\n");
            return -1;
        }
        Tree* firstNodeList = NULL;
        //convertNode(node1, &list);
        firstNodeList = convert(node1, list);
        if (firstNodeList == NULL)
        {
            printf("firstNodeList is NULL\n");
            return -1;
        }
        printRightList(firstNodeList);
        printLeftList(firstNodeList);
        return 0;
    }

 

 
4 運(yùn)行結(jié)果

    we will print list from left to right
    value is 0
    value is 1
    value is 2
    value is 3
    value is 4
    value is 5
    value is 6
    value is 7
    we will print list from right to left
    value is 7
    value is 6
    value is 5
    value is 4
    value is 3
    value is 2
    value is 1
    value is 0
     
     

 
 




 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)