输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建 任何新的结点，只能调整树中结点指针的指向

题目要求将输入的一棵二叉搜索树转换成一个排列的双向链表，不能创建任何新的结点，只能修改树中结点的指针指向。具体实现时，需要调整树中结点的指针指向，使得该树变成一个中序遍历的双向链表，其中每个结点都指向它在排列中的前驱和后继。

相关问题

编写一个代码：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

/* 代码示例 */ struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
}; TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL)
return NULL; TreeNode* pLastNodeInList = NULL;
ConvertNode(pRootOfTree,&pLastNodeInList); //pLastNodeInList指向双向链表的尾结点
//我们需要返回头结点
TreeNode* pHeadOfList = pLastNodeInList;
while(pHeadOfList!=NULL && pHeadOfList->left!=NULL)
pHeadOfList = pHeadOfList->left; return pHeadOfList;
} void ConvertNode(TreeNode* pNode, TreeNode** pLastNodeInList)
{
if(pNode==NULL)
return; TreeNode* pCurrent = pNode; //处理左子树
if(pCurrent->left!=NULL)
ConvertNode(pCurrent->left,pLastNodeInList); //处理当前结点
pCurrent->left = *pLastNodeInList;
if(*pLastNodeInList!=NULL)
(*pLastNodeInList)->right = pCurrent; *pLastNodeInList = pCurrent; //处理右子树
if(pCurrent->right!=NULL)
ConvertNode(pCurrent->right,pLastNodeInList);
}

用c语言编写一个完整的代码：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

#include <stdio.h>
#include <stdlib.h>/* 二叉搜索树结点定义 */
typedef struct BSTNode
{
int data;
struct BSTNode *lchild, *rchild;
} BSTNode;/* 双向链表结点定义 */
typedef struct DLLNode
{
int data;
struct DLLNode *prior, *next;
} DLLNode;/* 二叉搜索树与双向链表转换函数 */
DLLNode* BSTToDLL(BSTNode *root)
{
DLLNode *pFirst = NULL, *pLast = NULL;
if (root != NULL)
{
/* 将左子树转换为双向链表 */
if (root->lchild != NULL)
{
pFirst = BSTToDLL(root->lchild);
/* 左子树双向链表的最后一个结点为根结点 */
pLast = pFirst->prior;
/* 根结点指向左子树双向链表最后一个结点 */
root->lchild = pLast;
/* 左子树双向链表最后一个结点指向根结点 */
pLast->next = root;
}
else
{
/* 根结点为双向链表的第一个结点 */
pFirst = root;
}
/* 根结点指向其右子树 */
if (root->rchild != NULL)
{
/* 将右子树转换为双向链表 */
DLLNode *pRight = BSTToDLL(root->rchild);
/* 根结点指向右子树双向链表的第一个结点 */
root->rchild = pRight;
/* 右子树双向链表的第一个结点指向根结点 */
pRight->prior = root;
/* 双向链表的最后一个结点为右子树双向链表的最后一个结点 */
pLast = pRight->prior;
}
else
{
/* 根结点为双向链表的最后一个结点 */
pLast = root;
}
}
pFirst->prior = pLast;
pLast->next = pFirst;
return pFirst;
}int main()
{
return 0;
}答：我已经给出了一段用C语言编写的代码，它用于将一棵二叉搜索树转换为一个排序的双向链表。