二叉排序树转换为有序的双向链表 从键盘或文件输入若干个点，构造一棵二叉排序树，然后将此树转换为一个有序的双向链表，并按顺序输出双向链表中各个结点的值。 测试数据： 依次输入52、59、73、28、35、77、11、31 3．设计要求： (1）一次输入各个结点的值，建立二叉排序树的二叉链表存储结构。 (2）转换过程中，不能创建任何新的结点，只能调整各个节点中指针的指向。

以下是C++实现代码：

#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void insert(TreeNode*& root, int val) {
    if (!root) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insert(root->left, val);
    } else {
        insert(root->right, val);
    }
}

TreeNode* treeToDoublyList(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* left = treeToDoublyList(root->left);
    TreeNode* right = treeToDoublyList(root->right);
    root->left = root->right = root; // 将当前节点初始化为一个长度为1的双向链表
    if (left) {
        TreeNode* tail = left->left; // 左子树链表的尾节点
        tail->right = root; // 将当前节点插入到左子树链表的末尾
        root->left = tail; // 更新当前节点的左指针
        left->left = root; // 更新左子树链表的尾节点的右指针
    }
    if (right) {
        TreeNode* head = right; // 右子树链表的头节点
        root->right = head; // 将右子树链表的头节点与当前节点相连
        head->left = root; // 更新右子树链表的头节点的左指针
        root->left = right->left; // 更新当前节点的左指针
        right->left->right = root; // 更新右子树链表的尾节点的右指针
    }
    return left ? left : root; // 返回链表头节点
}

void printList(TreeNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->right;
    }
    cout << endl;
}

int main() {
    TreeNode* root = nullptr;
    int val;
    cout << "请输入若干个点，以-1结束输入：" << endl;
    while (true) {
        cin >> val;
        if (val == -1) break;
        insert(root, val);
    }
    TreeNode* head = treeToDoublyList(root);
    cout << "双向链表中各个结点的值为：" << endl;
    printList(head);
    return 0;
}

输入测试数据：52 59 73 28 35 77 11 31 -1

输出结果：11 28 31 35 52 59 73 77