题目描述：
-
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。
接下来的n行，每行为一个二叉搜索树的先序遍历序列，其中左右子树若为空则用0代替。
输出：
-
对应每个测试案例，
输出将二叉搜索树转换成排序的双向链表后，从链表头至链表尾的遍历结果。
样例输入：
-
1
2 1 0 0 3 0 0
样例输出：
-
1 2 3
思路：
1.二叉排序树的特点就是一个结点的左子树比它小，右子树比它大，所以可以根据中序遍历得到一棵排序的序列。
2.若不能创建新结点，那么我们只能去修改原始二叉树的指针。这里我们让指向左子树的指针变为链表中指向前一个结点的指针，而指向右子树的指针变为链表中指向后一个结点的指针。
3.结合上面两点，很容易写出一个递归的算法。如下:
代码：
/*
二叉排序树转双向链表
by Rowandjj
2014/8/6
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct _BNODE_
{
int data;
struct _BNODE_ *left;
struct _BNODE_ *right;
}BNode,*pNode,*pTree;
//---------------------------------------
//其实是一个中序遍历的过程，因为中序遍历二叉排序树可以得到有序序列
void ConvertNode(pTree pRoot,pNode *pTail)
{
if(pRoot == NULL)
{
return;
}
//左
pNode pCur = pRoot;
if(pCur->left != NULL)
{
ConvertNode(pCur->left,pTail);
}
//根
//left指针指向前一个，right指针指向后一个
pCur->left = *pTail;
if(*pTail != NULL)
{
(*pTail)->right = pCur;
}
*pTail = pCur;
//右
if(pCur->right != NULL)
{
ConvertNode(pCur->right,pTail);
}
}
//将二叉排序树转化为双向链表,返回双向链表头指针
pNode Convert(pTree pRoot)
{
if(pRoot == NULL)
{
return NULL;
}
pNode pTail = NULL;
ConvertNode(pRoot,&pTail);
pNode pHead = pTail;
//根据双向链表的尾找到其头指针
while(pHead != NULL && pHead->left != NULL)
{
pHead = pHead->left;
}
//返回双向链表头指针
return pHead;
}
//遍历双向链表
void DisplayLinkedList(pNode pHead)
{
if(pHead == NULL)
{
return;
}
pNode pTemp = pHead;
while(pTemp != NULL)
{
printf("%d ",pTemp->data);
pTemp = pTemp->right;
}
printf("\n");
}
//销毁双向链表
void DestroyList(pNode *pHead)
{
if(*pHead == NULL)
{
return;
}
pNode p = *pHead,q;
while(p != NULL)
{
q = p->right;
free(p);
p = q;
}
pHead = NULL;
}
//---------------------------------------
//先序构建二叉树
void CreateTree(pTree *pRoot)
{
int data;
scanf("%d",&data);
if(data == 0)
{
return;
}
*pRoot = (pNode)malloc(sizeof(BNode));
if(*pRoot == NULL)
{
exit(-1);
}
(*pRoot)->data = data;
(*pRoot)->left = NULL;
(*pRoot)->right = NULL;
CreateTree(&(*pRoot)->left);
CreateTree(&(*pRoot)->right);
}
//先序遍历排序树
void DisplayTree(pTree pRoot)
{
if(pRoot == NULL)
{
return;
}
printf("%d ",pRoot->data);
DisplayTree(pRoot->left);
DisplayTree(pRoot->right);
}
void DestroyTree(pTree *pRoot)
{
if(*pRoot == NULL)
{
return;
}
if((*pRoot)->left != NULL)
{
DestroyTree(&(*pRoot)->left);
}
if((*pRoot)->right != NULL)
{
DestroyTree(&(*pRoot)->right);
}
free(*pRoot);
*pRoot = NULL;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
if(n <= 0)
{
continue;
}
for(int i = 0; i < n; i++)
{
pTree pRoot = NULL;
CreateTree(&pRoot);
pNode pHead = Convert(pRoot);
if(pHead != NULL)
{
DisplayLinkedList(pHead);
}
DestroyList(&pHead);
}
}
return 0;
}
部分函数并没有使用，可以去掉
