二分查找树转化为排序的循环双链表

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

例如对于下面的二分查找树：

small pointer 其实也就是指向左孩子，large pointer指向右孩子，转化为双链表之后 small pointer应该指向前一个元素，large pointer应该指向后一个元素。转化为排序的循环双链表则为：

二：分析

二分查找树的中序遍历即为升序排列，问题就在于如何在遍历的时候更改指针的指向。一种简单的方法时，遍历二分查找树，讲遍历的结果放在一个数组中，之后再把该数组转化为双链表。如果题目要求只能使用O(1)内存，则只能在遍历的同时构建双链表，即进行指针的替换：

我们需要用递归的方法来解决，假定每个递归调用都会返回构建好的双链表，可把问题分解为左右两个子树。由于左右子树都已经是有序的，当前节点作为中间的一个节点，把左右子树得到的链表连接起来即可。

三：代码

#include<iostream>
#include<algorithm>

using namespace std;

struct Node
{
 int data;
 Node* lChild;
 Node* rChild;
 Node(int _data) 
 { 
  data = _data;
  lChild = rChild = nullptr; 
 }
};


Node* Append(Node* a, Node* b)//合并两个链表
{
 if (a == nullptr) return b;
 if (b == nullptr) return a;

 //分别得到两个链表的最后一个元素
 Node* aLast = a->lChild;
 Node* bLast = b->lChild;

 //将两个链表头尾相连
 aLast->rChild = b;
 b->lChild = aLast;

 a->lChild = bLast;
 bLast->rChild = a;

 return a;
}
//递归的解决二叉树转换为双链表
Node* TreeToList(Node* _root)
{
 if (_root == nullptr) return nullptr;

 //递归解决子树 ( 就相信他们一定会返回正确的结果 )
 Node* aList = TreeToList(_root->lChild);
 Node* bList = TreeToList(_root->rChild);

 //把根节点转换为一个节点的双链表。方便后面的链表合并
 _root->lChild = _root;
 _root->rChild = _root;

 //合并之后即为升序排列，顺序为 (aList, root, bList)
 aList = Append(aList, _root);
 aList = Append(aList, bList);

 return aList;
}
//构建二叉查找树
void TreeInsert(Node* _root, int newData)
{
 if (_root == nullptr) return;

 if (newData <= _root->data)
 {
  if (_root->lChild)
   TreeInsert(_root->lChild, newData);
  else
   _root->lChild = new Node(newData);
 }

 else
 {
  if (_root->rChild)
   TreeInsert(_root->rChild, newData);
  else
   _root->rChild = new Node(newData);
 }
}
//中序遍历二叉树
void PrintTree(Node* _root)
{
 if (!_root) return;

 PrintTree(_root->lChild);
 cout << _root->data << " ";
 PrintTree(_root->rChild);

}
//打印双链表
void PrintList(Node* _root)
{
 if (!_root) return;

 Node* end = _root;
 cout << _root->data << " ";
 _root = _root->rChild;

 while (_root != end)
 {
  cout << _root->data << " ";
  _root = _root->rChild;
 }

 cout << endl;
}

int main()
{
 /* 构建树结构如下：
           4
          / \
   2   5
     / \
    1   3
 */

 Node* root = new Node(4);
 TreeInsert(root, 2);
 TreeInsert(root, 1);
 TreeInsert(root, 3);
 TreeInsert(root, 5);

 cout << "二叉查找树中序遍历： ";
 PrintTree(root);
 
 cout << "\n循环双链表输出为： ";
 Node* head = TreeToList(root);
 PrintList(head);

 /*
 1 2 3 4 5
 1 2 3 4 5
 */
 return 0;
}

题目来自：http://www.acmerblog.com/great-tree-list-5814.html