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

只能修改节点中的指针，那么简单一点的情形，应该就是将二叉树节点中的lchild指针当做转化后双向链表中的prev指针，rchild指针当做next指针。

思路类似于严蔚敏《数据结构》中的线索二叉树，但是略不同的地方是，对于一个有左子树的节点来说，他的左孩子指针要指向左子树中最大的节点，而不是原本的左孩子。举个典型的例子，根节点应当指向左子树的右孩子的右孩子的右孩子(只要存在右孩子，就一直继续下去)。同理，对于一个有右子树的节点来说，原本的右孩子指针应当指向右子树中最小的节点，而不是原本的右孩子。

通过GetLeftMax来得到左子树中的最大节点，通过GetRightMin来得到右子树中的最小节点，然后把这两个节点和根节点正确的连接即可。每次连接要操作4个指针，分别是把左侧最大的rchild指向根节点，根节点的lchild指向左侧最大，右侧最小的lchild指向根节点，根节点rchild指向右侧最小。当然这是在这个根节点的左右子树都存在的情况下的讨论。

我的代码用C/C++实现。

以下是数据结构定义的代码：

#include 
     
      #include 
      
       using namespace std;#define NULL 0typedef struct TreeNode{	int nValue;	struct TreeNode* lchild;	struct TreeNode* rchild;}TreeNode;
      
     

　　

以下是转换算法的代码：

TreeNode* GetLeftMax(TreeNode* const);TreeNode* GetRightMin(TreeNode* const);TreeNode* LinkNode(TreeNode* const pRoot){	if (!pRoot) 		return NULL;	if (!pRoot->lchild && !pRoot->rchild)		return pRoot;	if (pRoot->lchild){		TreeNode* pLeftMax = GetLeftMax(pRoot);		pLeftMax->rchild = pRoot;		pRoot->lchild = pLeftMax;	}	if (pRoot->rchild){		TreeNode* pRightMin = GetRightMin(pRoot);		pRightMin->lchild = pRoot;		pRoot->rchild = pRightMin;	}	return pRoot;}TreeNode* GetLeftMax(TreeNode* const pRoot){	TreeNode* LeftMax = LinkNode(pRoot->lchild);	while (LeftMax->rchild)		LeftMax = LeftMax->rchild;	return LeftMax;}TreeNode* GetRightMin(TreeNode* const pRoot){	TreeNode* RightMin = LinkNode(pRoot->rchild);	while (RightMin->lchild)		RightMin = RightMin->lchild;	return RightMin;}TreeNode* GetHeadNodeOfDuLinkList(TreeNode* const pRoot){	TreeNode* pHead = LinkNode(pRoot);	if(pHead){		while(pHead->lchild)			pHead = pHead->lchild;	}	return pHead;}

　　

以下是测试用的代码，你也可以自己做一些改动：

static void BuildTree(TreeNode* &pRoot){	pRoot = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->nValue = 4;	pRoot->lchild = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->lchild->nValue = 2;	pRoot->lchild->lchild = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->lchild->lchild->nValue = 1;	pRoot->lchild->lchild->lchild = NULL;	pRoot->lchild->lchild->rchild = NULL;	pRoot->lchild->rchild = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->lchild->rchild->nValue = 3;	pRoot->lchild->rchild->lchild = NULL;	pRoot->lchild->rchild->rchild = NULL;	pRoot->rchild = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->rchild->nValue = 6;	pRoot->rchild->lchild = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->rchild->lchild->nValue = 5;	pRoot->rchild->lchild->lchild = NULL;	pRoot->rchild->lchild->rchild = NULL;	pRoot->rchild->rchild = (TreeNode*)malloc(sizeof(TreeNode));	pRoot->rchild->rchild->nValue = 7;	pRoot->rchild->rchild->lchild = NULL;	pRoot->rchild->rchild->rchild = NULL;}static void DeleteTree(TreeNode* pRoot){	if(!pRoot)		return;	if(pRoot->lchild)		DeleteTree(pRoot->lchild);	if(pRoot->rchild)		DeleteTree(pRoot->rchild);	if(!pRoot->lchild && !pRoot->rchild)		free(pRoot);}static void DeleteDuLinkList(TreeNode* pHead){	if(!pHead)		return;	else{		TreeNode* pNext = NULL;		while(pHead->rchild){			pNext = pHead->rchild;			free(pHead);			pHead = pNext;		}		free(pHead);	}}static void PrintDuLinkList(TreeNode* const pHead){	if(!pHead)		return;	else{		TreeNode* pTemp = pHead;		do{			cout << pTemp->nValue <
     
      rchild;		}while(pTemp);	}}int main(){	TreeNode* pRoot = NULL;	BuildTree(pRoot);	TreeNode* pHead = GetHeadNodeOfDuLinkList(pRoot);	PrintDuLinkList(pHead);	DeleteDuLinkList(pHead);	return 0;}
     

　　

只是跟书上给的不太一样。