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

1 問題

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

 

 
2 分析

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

 

 
3 代碼實現(xià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);
        }
        //這里就要進行我們每個節(jié)點的前后正確的指向了
        pCurrent->left = *lastNodeList;
        if (*lastNodeList != NULL)
        {
            (*lastNodeList)->right = pCurrent;
        }
        *lastNodeList = pCurrent;
     
        if (pCurrent->right != NULL)
        {
            convertNode(pCurrent->right, lastNodeList);
        }
    }
    
     
    /*
     * 把翻轉(zhuǎn)好的雙向鏈表尾巴節(jié)點移動到鏈表頭
     */
    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);
        //因為這個時候lastNodeList已經(jī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é)點移動為鏈表的尾巴
        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 運行結(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)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)