一、问题描述
输入一棵二叉查找树，将该二叉查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
【举例】
10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16
二、解题思路
题目要求不能创建任何新的结点，只需要调整指针的指向，那么就意味着可直接利用二叉树的结点，通过变更结点的左右孩子的指向，来生成双链表的逻辑关系。问题就变成了：
找当前root结点的左孩子最大的结点left_max，和找当前root结点的右孩子最大的结点right_max然后变更各自的指向，依次递归，然后变更指针指向关系： left_max->rchild = root - root->lchild = left_max right_max->lchild = root - root->rchild = right_max
三、解题算法
/******************************************
author:tmw
date:2018-10-25
******************************************/
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTreeNode
{
int data;
struct BiTreeNode* lchild;
struct BiTreeNode* rchild;
}BiTreeNode;
BiTreeNode* Tree2Dlink(BiTreeNode* root)
{
if(root == NULL) return NULL;
BiTreeNode* leftMax = root->lchild;
BiTreeNode* rightMin = root->rchild;
/**找到当前root结点排序后的前后两个元素**/
while(leftMax!=NULL && leftMax->rchild!=NULL)
leftMax = leftMax->rchild;
while(rightMin!=NULL && rightMin->lchild!=NULL)
rightMin = rightMin->lchild;
/**分别对左右子树做递归**/
Tree2Dlink(root->lchild);
Tree2Dlink(root->rchild);
/**变更指向，注意考虑空节点的情况**/
if(leftMax!=NULL)
leftMax->rchild = root;
if(rightMin!=NULL)
rightMin->lchild = root;
root->lchild = leftMax;
root->rchild = rightMin;
return root;
}
梦想还是要有的，万一实现了呢~~~~~~~~ヾ(◍°∇°◍)ﾉﾞ~~~~~
