แปลง Binary Tree เป็น Threaded Binary Tree โดยใช้ Queue ใน C++

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

เราจะได้รับ Binary Tree มา 1 ต้น งานคือแปลงต้นไม้นั้นให้กลายเป็น Threaded Binary Tree โดยเพิ่มเส้นทางเพิ่มเติมสำหรับการท่อง Inorder ให้เร็วขึ้น ด้วยความช่วยเหลือจาก Queue

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

#include <iostream>
#include <queue>
using namespace std;

// โครงสร้างโหนดสำหรับ Threaded Tree
struct Node {
    int key;
    Node *left, *right;
    bool isThreaded;
};

// ใส่ลำดับ Inorder ลงใน Queue
void convert_queue(Node* root, std::queue<Node*>* q) {
    if (root == NULL)
        return;
    if (root->left)
        convert_queue(root->left, q);
    q->push(root);
    if (root->right)
        convert_queue(root->right, q);
}

// ท่อง Queue และสร้าง Threaded Tree
void create_threadedtree(Node* root, std::queue<Node*>* q) {
    if (root == NULL)
        return;
    if (root->left)
        create_threadedtree(root->left, q);
    q->pop();
    if (root->right)
        create_threadedtree(root->right, q);
    // ถ้า right pointer เป็น NULL ให้ชี้ไปยัง Inorder Successor
    else {
        root->right = q->front();
        root->isThreaded = true;
    }
}

// ฟังก์ชันหลักแปลง Tree เป็น Threaded
void createThreaded(Node* root) {
    std::queue<Node*> q;
    convert_queue(root, &q);
    create_threadedtree(root, &q);
}

Node* leftMost(Node* root) {
    while (root != NULL && root->left != NULL)
        root = root->left;
    return root;
}

// ท่อง Inorder ของ Threaded Tree
void inOrder(Node* root) {
    if (root == NULL)
        return;
    Node* cur = leftMost(root);
    while (cur != NULL) {
        cout << cur->key << " ";
        // ถ้าเป็น threaded node ให้ไปยัง inorder successor
        if (cur->isThreaded)
            cur = cur->right;
        else
            cur = leftMost(cur->right);
    }
}

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

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    createThreaded(root);
    cout << "Traversing threaded tree :\n";
    inOrder(root);
    return 0;
}

ผลลัพธ์

Traversing threaded tree : 4 2 5 1 6 3 7