【整理】把二元查找树转变成排序的双向链表

整理自：

1. July @CSDN http://blog.csdn.net/v_JULY_v/article/details/6278484

2.剑指offer by 何海涛 http://zhedahht.blog.163.com/blog/static/254111742007127104759245/

修改 by sail2011@新浪微薄：http://weibo.com/sail2011

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

　　比如将二元查找树
10
/ \
6 14
/ \ /　 \
4 8 12 16
转换成双向链表

4=6=8=10=12=14=16。

　　分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。下面我们用两种不同的递归思路来分析。

何海涛：

在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。由于这两种结点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此在理论上有可能实现二叉搜索树和排序的双向链表的转换。在搜索二叉树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点指针。接下来我们考虑该如何转换。

由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每一个结点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。当遍历到根结点的时候，我们把树看成三部分:值为10的结点、根结点值为6的左子树、根结点值为14的右子树。根据排序链表的定义，值为10的结点将和它的左子树的最大一个结点(即值为8的结点)链接起来，同时它还将和右子树最小的结点(即值为12的结点)链接起来。

按照中序遍历的顺序，当我们遍历转换到根结点(值为10的结点)时，它的左子树已经转换成一个排序的链表，并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，此时链表中的最后一个结点就是10了。接着我们去遍历转换右子树，并把根结点和右子树中最小的结点链接起来。至于怎么去转换它的左子树和右子树，由于遍历和转换过程是一样的，我们很自然地想到可以用递归。

本题考点和分析：

考查应聘者分析复杂问题的能力。无论是二叉树还是双向链表，都有很多指针。要实现这两种不同数据结构的转换，需要调整大量的指针，因此这个过程会很复杂。为了把这个复杂的问题分析清楚，我们可以把树分为三个部分:根结点、左子树和右子树，然后把左子树中最大的结点、根结点、右子树中最小的结点链接起来。至于如何把左子树和右子树内部的结点链接成链表，那和原来的问题的实质是一样的，因此可以递归解决。解决这个问题的关键在于把一个大的问题分解成几个小问题，并递归地解决小问题。

　　思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

　　思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

参考代码：

首先我们定义二元查找树结点的数据结构如下：

sail2011 注：
      先从宏观上来考虑问题，把中序遍历和递归的流程想清楚！ 对于july的第一个程序，在每一次ergodicBSTree(pCurrent->m_pLeft)执行后都要返回一次，也就是第一次pCurrent是1号节点，然后pCurrent是2号节点，再然后是4号节点。。。。。。
    4
 /     \
2         6
/   \     /
1   3   5
 
july程序：
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight){       if(!pNode)             return NULL;                                                               BSTreeNode *pLeft = NULL;   //用来存储当前结点的左子树的最后一个结点      BSTreeNode *pRight = NULL;  //用来存储当前结点的右子树的第一个结点                                                              // 如果当前结点有左子树就转换其左子树      if(pNode->m_pLeft)             //存储当前结点的左子树的最后一个结点        pLeft = ConvertNode(pNode->m_pLeft, false);                                                               // 连接左子树中最大的结点即pLeft到当前结点      if(pLeft)       {             pLeft->m_pRight = pNode;             pNode->m_pLeft = pLeft;       }                                                               // 如果当前结点有右子树就转换其右子树      if(pNode->m_pRight)             //存储当前结点的右子树的第一个结点            pRight = ConvertNode(pNode->m_pRight, true);                                                               // 连接右子树中最小的结点即pRight到当前结点      if(pRight)       {             pNode->m_pRight = pRight;             pRight->m_pLeft = pNode;       }                                                               BSTreeNode *pTemp = pNode;                                                               // 如果当前结点是某个右子树就返回该右子树中最小的结点      if(asRight)       {             while(pTemp->m_pLeft)                   pTemp = pTemp->m_pLeft;       }       // 如果当前结点是某个左子树就返回该左子树中最大的结点      else      {             while(pTemp->m_pRight)                   pTemp = pTemp->m_pRight;       }                                                             //返回结点地址给ConvertNode      //左子树为最后一个结点，右子树为第一个结点      return pTemp; }


整理自：1. July @CSDNhttp://blog.csdn.net/v_JULY_v/article/details/6278484
2.剑指offer by 何海涛  http://zhedahht.blog.163.com/blog/static/254111742007127104759245/
修改by sail2011@新浪微薄：http://weibo.com/sail2011