1、题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
输入：
Paste_Image.png
输出：
1<=>2<=>3<=>4<=>5<=>6<=>7
解题思路：
利用二叉树的中序遍历，不断向空的双向链表中插入（改变lchild和rchild指针）新结点。
①
代码：
#include "stdafx.h"
#include "stdlib.h"
typedef struct TreeNode{
char value;
struct TreeNode * LeftChild;
struct TreeNode * RightChild;
}TreeNode,*Tree;
int flag=0;//判断是否为链表的首结点
Tree first,tail;//分别指向链表头结点和尾结点的指针
/*****创建二叉树*****/
Tree CreatTree()
{
char value;
TreeNode * Node;
scanf("%c",&value);
if(value=='#')
Node=NULL;
else{
Node=(TreeNode *)malloc(sizeof(TreeNode));
Node->value=value;
Node->LeftChild=CreatTree();
Node->RightChild=CreatTree();
}
return Node;
}
/*****创建链表*****/
void Link(Tree tree)
{
if(flag==0) //flag==0,Link函数第一次被调用，此时链表为空
{
flag=1;
tail=first=tree;
tail->LeftChild=first->LeftChild=NULL;
tail->RightChild=first->RightChild=NULL;
}
else
{
tail->RightChild=tree;
tree->LeftChild=tail; //在创建链表过程中，改变了当前结点的左孩子指针，虽然破坏了二叉树的结构，但不影响其后续的中序遍历。
tail=tree;
}
}
void MiddleTravel(Tree tree)
{
if(tree)
{
MiddleTravel(tree->LeftChild);
Link(tree);
MiddleTravel(tree->RightChild);
}
}
void Print()
{
Tree n;
n=first;
while(n)
{
printf("%c\t",n->value);
n=n->RightChild;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Tree tree;
int high;
printf("输入二叉树节点:");
tree=CreatTree();
printf("\n排序后:");
MiddleTravel(tree);
Print();
system("PAUSE");
return 0;
}
