劍指offer之二叉搜尋樹和雙向連結清單

1 問題

比如我們搜尋二叉樹如下，我們需要變成雙向連結清單

2 分析

我們知道這個變成雙向連結的時候是按照樹的中序周遊列印的，我們隻需要在中序周遊列印的時候操作該節點，我們可以用臨時變量儲存這個節點，同時我們也需要單獨增加一個連結清單節點變量，我們需要保證這個節點的左邊指向是該連結清單節點，然後該連結清單節點的右指向是這個節點，然後我們再把這個節點指派給這個連結清單節點，就這樣一直移動下去即可。

3 代碼實作

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;
 
/*
 * 把搜尋二叉樹轉成雙向連結清單，我們按照中序周遊
 */
void convertNode(Tree* node, Tree** lastNodeList)
{
    if (node == NULL)
        return;
    Tree* pCurrent = node;
    if (pCurrent->left != NULL)
    {
        convertNode(pCurrent->left, lastNodeList);
    }
    //這裡就要進行我們每個節點的前後正确的指向了
    pCurrent->left = *lastNodeList;
    if (*lastNodeList != NULL)
    {
        (*lastNodeList)->right = pCurrent;
    }
    *lastNodeList = pCurrent;
 
    if (pCurrent->right != NULL)
    {
        convertNode(pCurrent->right, lastNodeList);
    }
}
 
 
 
/*
 * 把翻轉好的雙向連結清單尾巴節點移動到連結清單頭
 */
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已經到了雙向連結清單尾巴，我們需要移動到連結清單頭
    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;
    //先把連結清單頭結點移動為連結清單的尾巴
    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 運作結果

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