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

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/102493455