Inorder Traversal ของ Threaded Binary Tree ใน C++

ภาพรวม Threaded Binary Tree

Threaded Binary Tree เป็น Binary Tree ที่นำ Pointer ว่าง (NULL) ของโหนดที่ไม่มีลูกซ้ายหรือขวา ไปชี้ไปยัง Inorder Predecessor หรือ Inorder Successor แทน เพื่อให้สามารถท่อง Inorder ได้โดยไม่ต้องใช้ Stack หรือ Recursion

ประเภทของ Threaded Binary Tree

โครงสร้างโหนด Fully Threaded

struct Node {
    int data;
    Node* left;
    Node* right;
    bool leftThread;   // true = left เป็น thread (ชี้ predecessor)
    bool rightThread;  // true = right เป็น thread (ชี้ successor)
};

แนวคิด Inorder Traversal แบบ Threaded

ปกติ Inorder ใช้ Stack/Recursion: Left → Root → Right

แบบ Threaded: เริ่มจาก Leftmost Node → ตาม Right Thread ไป Successor → ถ้า Right เป็น Child ให้ไป Leftmost ของซับทรีขวา

อัลกอริทึม Inorder Traversal (Non-Recursive)

INORDER():
    current = leftmost(root)  // หาโหนดซ้ายสุด
    WHILE current != root:    // root เป็น dummy header
        PRINT current->data
        IF current->rightThread:
            current = current->right  // ตาม thread ไป successor
        ELSE:
            current = leftmost(current->right)  // ไปซ้ายสุดของซับทรีขวา

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    bool leftThread;
    bool rightThread;
    
    Node(int val) : data(val), left(nullptr), right(nullptr), 
                    leftThread(true), rightThread(true) {}
};

class ThreadedBinaryTree {
private:
    Node* root;  // Dummy header node
    
    // หาโหนดซ้ายสุดจากโหนดที่กำหนด
    Node* leftmost(Node* node) {
        if (!node) return nullptr;
        while (!node->leftThread) {
            node = node->left;
        }
        return node;
    }
    
public:
    ThreadedBinaryTree() {
        root = new Node(0);  // Dummy header
        root->left = root->right = root;
        root->leftThread = true;
        root->rightThread = false;  // Right ชี้ไป root จริง (ถ้ามี)
    }
    
    // Insert แบบ BST พร้อม Thread
    void insert(int key) {
        Node* parent = root;
        Node* current = root->right;  // เริ่มจาก root จริง (ถ้ามี)
        
        // หาตำแหน่ง Insert (เหมือน BST)
        while (current != root) {
            parent = current;
            if (key < current->data) {
                if (current->leftThread) break;
                current = current->left;
            } else if (key > current->data) {
                if (current->rightThread) break;
                current = current->right;
            } else {
                return;  // Duplicate, ไม่ Insert
            }
        }
        
        // สร้างโหนดใหม่
        Node* newNode = new Node(key);
        
        if (parent == root && root->rightThread) {
            // Tree ว่าง
            newNode->left = newNode->right = root;
            root->right = newNode;
            root->rightThread = false;
        } else if (key < parent->data) {
            // Insert เป็น Left Child
            newNode->left = parent->left;
            newNode->right = parent;
            parent->left = newNode;
            parent->leftThread = false;
        } else {
            // Insert เป็น Right Child
            newNode->left = parent;
            newNode->right = parent->right;
            parent->right = newNode;
            parent->rightThread = false;
        }
    }
    
    // Inorder Traversal แบบ Threaded (Non-recursive)
    void inorder() {
        Node* current = leftmost(root->right);  // เริ่มจากโหนดซ้ายสุดจริง
        
        while (current != root) {
            cout << current->data << " ";
            
            if (current->rightThread) {
                current = current->right;  // ตาม Thread
            } else {
                current = leftmost(current->right);  // ไปซ้ายสุดของ Right Subtree
            }
        }
        cout << endl;
    }
};

int main() {
    ThreadedBinaryTree tbt;
    
    cout << "Inserting: 56, 23, 89, 85, 20, 30, 12\n";
    tbt.insert(56);
    tbt.insert(23);
    tbt.insert(89);
    tbt.insert(85);
    tbt.insert(20);
    tbt.insert(30);
    tbt.insert(12);
    
    cout << "Inorder Traversal: ";
    tbt.inorder();  // 12 20 23 30 56 85 89
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Inserting: 56, 23, 89, 85, 20, 30, 12
Inorder Traversal: 12 20 23 30 56 85 89

การทำงานขั้นตอน (Step-by-step)

1. Insert 56: กลายเป็น Root จริง (child ของ dummy header)
2. Insert 23: น้อยกว่า 56 → Left Child ของ 56
3. Insert 89: มากกว่า 56 → Right Child ของ 56
4. Insert 85: น้อยกว่า 89 → Left Child ของ 89
5. Insert 20: น้อยกว่า 56, มากกว่า 23 → Right Child ของ 23
6. Insert 30: น้อยกว่า 56, มากกว่า 23, มากกว่า 20 → Right Child ของ 20
7. Insert 12: น้อยกว่า 56, น้อยกว่า 23 → Left Child ของ 23

Inorder: 12 (Leftmost) → 23 → 20 → 30 → 56 → 85 → 89

ความได้เปรียบของ Threaded Binary Tree

ข้อจำกัด

• Insert/Delete ซับซ้อนกว่า เพราะต้องปรับ Thread Pointers
• ใช้หน่วยความจำเพิ่มสำหรับ Boolean Flags
• ไม่เหมาะกับต้นไม้ที่มีการ Insert/Delete บ่อย
• เหมาะกับต้นไม้ที่สร้างเสร็จแล้ว ท่องบ่อย (Read-heavy)

Priority Queue ใน C++ STL

Doubly Linked Circular List ใน C++