Projects 1. Convert a binary search tree into a sorted circular doubly linked list 【Problem Description】 Given a binary search tree, you need to convert it into a circular doubly linked list, the elements in the linked list are sorted. For example, a binary search tree in Fig.1 is converted into a sorted circular doubly linked list in Fig.2. 【Basic Requirements】 The input data is a set of data elements to build a binary search tree, you should design algorithms to realize the conversion process and verify the accuracy of your code on multiple test data. The output includes the following: (1) Print the binary search tree (2) Traverse the binary search tree (3) Print the converted doubly linked list (4) Output all elements of the doubly linked list in positive and reverse order

【Solution】
Here is a C++ implementation of the solution to the problem:

#include <iostream>
#include <stack>

using namespace std;

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

class Solution {
public:
    TreeNode* treeToDoublyList(TreeNode* root) {
        if (!root) {
            return NULL;
        }
        stack<TreeNode*> s;
        TreeNode* p = root;
        TreeNode* pre = NULL;
        TreeNode* head = NULL;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            s.pop();
            if (pre) {
                pre->right = p;
                p->left = pre;
            } else {
                head = p;
            }
            pre = p;
            p = p->right;
        }
        head->left = pre;
        pre->right = head;
        return head;
    }
};

void printBST(TreeNode* root) {
    if (root) {
        printBST(root->left);
        cout << root->val << " ";
        printBST(root->right);
    }
}

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

void printListReverse(TreeNode* head) {
    TreeNode* p = head->left;
    do {
        cout << p->val << " ";
        p = p->left;
    } while (p != head->left);
    cout << endl;
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);

    Solution s;
    TreeNode* head = s.treeToDoublyList(root);

    cout << "Binary Search Tree: ";
    printBST(root);
    cout << endl;

    cout << "Doubly Linked List: ";
    printList(head);

    cout << "Doubly Linked List in Reverse Order: ";
    printListReverse(head);

    return 0;
}

【Explanation】
To convert a binary search tree into a sorted circular doubly linked list, we can use a stack to perform an inorder traversal of the binary search tree. During the traversal, we maintain a pointer to the previous node visited and link the current node to the previous node. After the traversal, we link the head and tail of the linked list to form a circular doubly linked list. Finally, we can print the binary search tree, traverse the doubly linked list, and output all elements in positive and reverse order.

【Example】

Input:

    4
   / \
  2   5
 / \
1   3

Output:

Binary Search Tree: 1 2 3 4 5
Doubly Linked List: 1 2 3 4 5
Doubly Linked List in Reverse Order: 5 4 3 2 1