แปลง Binary Tree เป็น Circular Doubly Linked List ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง Binary Tree ให้กลายเป็น Circular Doubly Linked List

เราจะได้รับ Binary Tree มา 1 ต้น งานคือแปลงโหนด left และ right ให้กลายเป็น previous และ next ตามลำดับ และใช้ลำดับ Inorder ของ Binary Tree เป็นลำดับของ Circular Linked List

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

// โครงสร้างโหนดของ Binary Tree
struct Node {
    struct Node *left, *right;
    int data;
};

// ต่อ rightList ไปท้าย leftList
Node* concatenate(Node* leftList, Node* rightList) {
    // ถ้ารายการหนึ่งว่าง ให้คืนอีกรายการ
    if (leftList == NULL)
        return rightList;
    if (rightList == NULL)
        return leftList;

    Node* leftLast = leftList->left;
    Node* rightLast = rightList->left;

    // เชื่อม leftList กับ rightList
    leftLast->right = rightList;
    rightList->left = leftLast;
    leftList->left = rightLast;
    rightLast->right = leftList;

    return leftList;
}

// แปลงเป็น Circular Linked List และคืนหัว
Node* bTreeToCList(Node* root) {
    if (root == NULL)
        return NULL;

    Node* left = bTreeToCList(root->left);
    Node* right = bTreeToCList(root->right);

    // ทำให้ root เป็น circular list เดียว
    root->left = root->right = root;

    return concatenate(concatenate(left, root), right);
}

// แสดง Circular Linked List
void print_Clist(Node* head) {
    cout << "Circular Linked List is :\n";
    Node* itr = head;
    do {
        cout << itr->data << " ";
        itr = itr->right;
    } while (head != itr);
    cout << "\n";
}

// สร้างโหนดใหม่และคืนที่อยู่
Node* newNode(int data) {
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    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;
}

ผลลัพธ์

Circular Linked List is : 25 12 30 10 36 15