剑指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
     
     

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)