1

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;
}