（一）把二元查找树转变成排序的双向链表

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 比如将二元查找树
10
/ \
6 14
/ \ /　 \
4 8 12 　16
转换成双向链表

4=6=8=10=12=14=16。

分析：本题是微软面试100题的第一题，由于树本身定义就属于递归式定义，所以很多与树相关的题目都是用递归的思路来解决，本题亦是如此。下面我们用两种不同的递归思路来分析。

思路一：中序遍历的顺序即是我们所要建立链表的顺序。所以可以在中序遍历整棵树的同时，通过调整节点的指针来将其转换为双向链表。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。<wbr></wbr>

思路二：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树，将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最后链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

#include<stdio.h>
#include<stdlib.h>
struct BiTreeNode
{
int value;
BiTreeNode *left;
BiTreeNode *right;
};

void Convert(BiTreeNode *& head, BiTreeNode *& tail, BiTreeNode *root)
{
BiTreeNode *left, *right;
if (root == NULL)
{
head = NULL;
tail = NULL;
return;
}
Convert(head, left, root->left);
Convert(right, tail, root->right);
if (left!=NULL)
{
left->right = root;
root->left = left;
}
else
{
head = root;
}
if (right!=NULL)
{
root->right=right;
right->left = root;
}
else
{
tail = root;
}

}

BiTreeNode * treeToLinkedList(BiTreeNode * root)
{
BiTreeNode * head, * tail;
Convert(head, tail, root);
return head;//返回链表的头指针
}

/*递归创建二叉排序树，以'-1'结束*/
BiTreeNode * CreateBSTree()
{
int data;
BiTreeNode * tr;
scanf("%d",&data);
if(data==-1)
{
return NULL;
}
else
{
tr = (BiTreeNode *)malloc(sizeof(BiTreeNode));
tr->value=data;
tr->left = CreateBSTree();
tr->right = CreateBSTree();

return tr;
}
}

//中序遍历二叉树
void InOrderTraverse(BiTreeNode * root)
{
if(root->left)
InOrderTraverse(root->left);

if(root)
printf("%d ",root->value);

if(root->right)
InOrderTraverse(root->right);
}
int main()
{
BiTreeNode * root=CreateBSTree();

InOrderTraverse(root);
printf("\n");

BiTreeNode *head=treeToLinkedList(root);

BiTreeNode * temp=head;
while(temp!=NULL)
{
printf("%d ",temp->value);
temp=temp->right;
}

getchar();
return 0;
}