给定一个二叉排序树，把该二叉排序树转换成从小到大的双向链表

二叉排序树又叫二叉搜索树。它除了具有一般二叉树的性质还有
1、如果二叉树的左子树不为空，那么左子树的所有节点的值都比根节点值要小。
2、如果二叉树的左子树不为空，那么左子树的所有节点的值都比根节点值要小。
3、二叉排序树的左右子树也都是二叉排序树。如下图所示：

我们现在要把一个二叉树变为一个有序的双向链表。比如上图可以变为：
1=3=4=6=7=8=10=13=14
定义二叉排序树的结构：
typedef struct Node
{
int val;
Node *lChild;
Node *rChild;
Node()
{
this->lChild = nullptr;
this->rChild = nullptr;
}
Node(int val)
{
this->val = val;
this->lChild = nullptr;
this->rChild = nullptr;
}
}TreeNode;
二叉排序树的插入算法
void insertNode(TreeNode *&node, int val)//必须加&号，这个是指针的引用。因为后面会涉及到为指针申请新的内存并赋值。重点敲黑板：当我们把一个指针做为参数传一个方法时，其实是把指针的复本传递给了方法，也可以说传递指针是指针的值传递。如果我们在方法内部修改指针会出现问题，在方法里做修改只是修改的指针的copy而不是指针本身，原来的指针还保留着原来的值。当然也可以传递指针的指针。
{
if (node == nullptr)
{
node = new TreeNode(val);
}
else
{
if (val >= node->val)
{
insertNode(node->rChild, val);
}
else
{
insertNode(node->lChild, val);
}
}
}
如何把二叉排序树转换成从小到大的双向链表，在二叉排序树中我们知道，左子树都是比根节点小的，右子树都是比根节点大的。这样我们通过递归和分而治之的算法遍历二叉排序树，可以把左子树排到根节点的左边，右子树排到根节点的右边。
代码如下：
TreeNode *ConvertTree2Link(TreeNode *node)
{
if (node == nullptr)
{
return nullptr;
}
TreeNode *lChild = nullptr;
if (node->lChild)
{
lChild = ConvertTree2Link(node->lChild);//存在左子树，则递归转换左子树。
}
TreeNode *rChild = nullptr;
if (node->rChild)
{
rChild = ConvertTree2Link(node->rChild);//存在右子树，则递归转换右子树。
}
if (rChild)
{
node->rChild = rChild;
rChild->lChild = node;//右子树都比node的值大，所以直接拼接即可。
}
if (lChild)
{
TreeNode *lChildTemp = lChild;
while (lChildTemp->rChild != nullptr)
{
lChildTemp = lChildTemp->rChild;//左子树都比node的值小，需要node和最后一个节点拼接。。
}
lChildTemp->rChild = node;
node->lChild = lChildTemp;
return lChild;//直接返回左子树的转换节点即可。因为最小。
}
return node;
}
验证代码如下：
int main()
{
TreeNode *root = nullptr;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++)
{
int val = rand() % 50;
cout << val << " ";
insertNode(root, val);
}
cout << endl;
TreeNode *Link = ConvertTree2Link(root);
TreeNode *test1 = Link;
while (test1)
{
cout << test1->val << " ";
test1 = test1->rChild;
}
cout << endl;
test1 = Link;
while (test1->rChild)
{
test1 = test1->rChild;
}
while (test1)
{
cout << test1->val << " ";
test1 = test1->lChild;
}
cout << endl;
system(“pause”);
return 0;
}
验证截图：

二叉排序树的中序遍历就是一个排序号的数组，我们也可以通过中序遍历的方法来构造该双向链表，实现题目的要求。