二叉查找树转换为双向链表（递归方法实现）

题目要求：将二叉查找树转换成排序的双向链表，不能创建新节点，只调整指针。

查找树的结点定义如下：

class Node
{
public:
     Node(int x):left(NULL),right(NULL),data(x){};
     Node * left;
     Node * right;
     int data;
};

既然是树，其定义本身就是递归的，自然用递归算法处理就很容易。
将根结点的左子树和右子树转换为有序的双向链表，然后根节点的left指针指向左子树结果的最后一个结点，同时左子树最后一个结点的right指针指向根节点；根节点的right指针指向右子树结果的第一个结点，同时右子树第一个结点的left指针指向根节点。

/*
参数：
结点的指针，以r所指结点为根节点的树转换成双向链表后，
链表第一个结点的指针first，链表最后一个结点的指针last
*/
void Convert(Node * r,Node * & first,Node * & last)
{
    //左子树和右子树结果的指针
    Node *firstL,*lastL,*firstR,*lastR;
    if(r==NULL) return;
    Convert(r->left,firstL,lastL);
    Convert(r->right,firstR,lastR);

    if(r->left==NULL)
    {
        /*如果左子树是空的，那么以r所指结点为根结点的树
        转换结果的第一个结点的指针就是r*/
        first=r;
        r->left=NULL;
    }
    else
    {
        /*以r所指结点为根节点的树转换成双向链表后，链表第一个结点的指针first
        就是左子树结果的第一个结点的指针firstL*/
        first=firstL;
        /*r->left指向左子树结果的最后一个结点，
        同时左子树最后一个结点的right指针指向r所指结点*/
        r->left=lastL;
        lastL->right=r;
    }
    if(r->right==NULL)
    {
        /*如果右子树是空的，那么以r所指结点为根结点的树
        转换结果的最后一个结点的指针就是r*/
        last=r;
        r->right=NULL;
    }
    else
    {
        /*以r所指结点为根节点的树转换成双向链表后，链表最后一个结点的指针last
        就是右子树结果的最后一个结点的指针lastR*/
        last=lastR;
        /*r->right向右子树结果的第一个结点，
        同时右子树第一个结点的right指针指向r所指结点*/
        r->right=firstR;
        firstR->left=r;
    }
}