Chuyển đổi cây nhị phân thành danh sách liên kết đôi vòng (Circular Doubly Linked List) trong C++

Chuyển đổi cây nhị phân thành danh sách liên kết đôi vòng (CDLL) sao cho thứ tự các nút trong CDLL tuân theo thứ tự inorder của cây. Con trỏ left đóng vai trò prev, con trỏ right đóng vai trò next.

Ý tưởng: Sử dụng đệ quy. Với mỗi nút, chuyển đổi cây con trái và phải thành CDLL, sau đó nối: leftCDLL + nút hiện tại + rightCDLL.

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

struct Node {
    Node *left, *right;
    int data;
};

// Nối hai CDLL: leftList và rightList
Node* concatenate(Node* leftList, Node* rightList) {
    if (!leftList) return rightList;
    if (!rightList) return leftList;
    Node* leftLast = leftList->left;
    Node* rightLast = rightList->left;
    leftLast->right = rightList;
    rightList->left = leftLast;
    leftList->left = rightLast;
    rightLast->right = leftList;
    return leftList;
}

// Chuyển cây thành CDLL, trả về head
Node* bTreeToCList(Node* root) {
    if (!root) return nullptr;
    Node* left = bTreeToCList(root->left);
    Node* right = bTreeToCList(root->right);
    root->left = root->right = root; // nút đơn lẻ thành CDLL tròn
    return concatenate(concatenate(left, root), right);
}

void print_Clist(Node* head) {
    if (!head) return;
    cout << "Danh sach lien ket doi vong: ";
    Node* itr = head;
    do {
        cout << itr->data << " ";
        itr = itr->right;
    } while (itr != head);
    cout << "\n";
}

Node* newNode(int data) {
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = nullptr;
    return temp;
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);
    Node* head = bTreeToCList(root);
    print_Clist(head);
    return 0;
}

Kết quả

Danh sach lien ket doi vong: 25 12 30 10 36 15