树(1)把二叉查找树转换成有序的双向链表

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

10
/ /
6 14
/ / / /
4 8 12 16

转换成双向链表
4=6=8=10=12=14=16。
基本思路：中序遍历
构造双向链表
c语言代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct BinaryTree//结构体定义方式
{
struct BinaryTree *pLeft;//c语言中不要忘记写这个struct 
struct BinaryTree *pRight;
int value;
}pNode,*NODE;
pNode *pListIndex;//做双向链表索引
pNode *pHead;//双向链表头节点
pNode *convertToLink(pNode *pCurrent);
pNode *create(int *a,int lo,int hi)//构造搜索二叉树
{
if (lo > hi) return NULL ;//这里再次强调，没有等号,有的话就错了
int mid = (lo+hi)/2;
    pNode *pHead = (NODE)malloc(sizeof(pNode));
    pHead->value = a[mid];
    pHead->pLeft = create(a,lo,mid-1);
    pHead->pRight = create(a,mid+1,hi);
return pHead;
}
void inOrder(pNode *pRoot)//中序遍历
{
if (pRoot == NULL) return ;
if (pRoot->pLeft != NULL)
        inOrder(pRoot->pLeft);
    convertToLink(pRoot);
// printf("%d",pRoot->value);
if (pRoot->pRight != NULL)
        inOrder(pRoot->pRight);
}
void convertToLink(pNode *pCurrent)//构造*双*向链表
{
    pCurrent->pLeft = pListIndex;
if (pListIndex == NULL)
        pHead = pCurrent;
else
        pListIndex->pRight = pCurrent;
    pListIndex = pCurrent;
    printf("%d\n",pCurrent->value);
}
int main()
{
int a[] = {4,6,8,10,12,14,16};//先排序
    pNode *pRoot = create(a,0,6);
    inOrder(pRoot);
return 0;
}

运行结果如下：
[root@localhost c++]# ./a.out
4
6
8
10
12
14
16