C++ Program: Threaded Binary Tree Implementation (Inorder Traversal Without Stack/Recursion)

Threaded Binary Tree เป็น Binary Tree ที่ Pointer NULL ของ Node ถูกแทนที่ด้วย "Thread" (Pointer) ไปยัง Inorder Predecessor/Successor ทำให้ Inorder Traversal ได้ใน O(N) Time, O(1) Space โดยไม่ต้องใช้ Stack หรือ Recursion

Types of Threading

Node Structure

struct Node {
    int key;
    Node *left, *right;
    bool leftThread, rightThread; // true = thread, false = child
    
    Node(int k) : key(k), left(nullptr), right(nullptr), 
                  leftThread(true), rightThread(true) {}
};

Operations

1. Insert

void insert(Node*& root, int key) {
    Node* parent = nullptr;
    Node* curr = root;
    
    // Find insertion point
    while (curr) {
        parent = curr;
        if (key < curr->key) {
            if (!curr->leftThread) curr = curr->left;
            else break;
        } else if (key > curr->key) {
            if (!curr->rightThread) curr = curr->right;
            else break;
        } else return; // Duplicate
    }
    
    Node* newNode = new Node(key);
    
    if (!parent) {
        root = newNode;
    } else if (key < parent->key) {
        newNode->left = parent->left;
        newNode->right = parent;
        parent->left = newNode;
        parent->leftThread = false;
    } else {
        newNode->left = parent;
        newNode->right = parent->right;
        parent->right = newNode;
        parent->rightThread = false;
    }
}

2. Inorder Successor

Node* inorderSuccessor(Node* node) {
    if (node->rightThread) return node->right;
    node = node->right;
    while (!node->leftThread) node = node->left;
    return node;
}

3. Inorder Traversal (O(1) Space!)

void inorderTraversal(Node* root) {
    if (!root) return;
    
    // Go to leftmost
    Node* curr = root;
    while (!curr->leftThread) curr = curr->left;
    
    while (curr) {
        cout << curr->key << " ";
        curr = inorderSuccessor(curr);
    }
    cout << "\n";
}

4. Search

bool search(Node* root, int key) {
    Node* curr = root;
    while (curr) {
        if (key < curr->key) {
            if (curr->leftThread) return false;
            curr = curr->left;
        } else if (key > curr->key) {
            if (curr->rightThread) return false;
            curr = curr->right;
        } else return true;
    }
    return false;
}

5. Delete (Complex - 3 Cases)

Case 1: Leaf Node (Both Threads) → Remove, Update Parent Thread

Case 2: One Child → Replace with Child, Fix Threads

Case 3: Two Children → Find Inorder Successor, Swap, Delete Successor (Case 1/2)

Complete Working Example (Menu-driven)

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

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

class ThreadedBST {
    Node* root;
    
public:
    ThreadedBST() : root(nullptr) {}
    
    void insert(int key) {
        Node *parent = nullptr, *curr = root;
        while (curr) {
            parent = curr;
            if (key < curr->key) {
                if (!curr->leftThread) curr = curr->left;
                else break;
            } else if (key > curr->key) {
                if (!curr->rightThread) curr = curr->right;
                else break;
            } else return;
        }
        
        Node* n = new Node(key);
        if (!parent) root = n;
        else if (key < parent->key) {
            n->left = parent->left; n->right = parent;
            parent->left = n; parent->leftThread = false;
        } else {
            n->left = parent; n->right = parent->right;
            parent->right = n; parent->rightThread = false;
        }
    }
    
    Node* inorderSuccessor(Node* n) {
        if (n->rightThread) return n->right;
        n = n->right;
        while (!n->leftThread) n = n->left;
        return n;
    }
    
    void inorder() {
        if (!root) return;
        Node* curr = root;
        while (!curr->leftThread) curr = curr->left;
        while (curr) {
            cout << curr->key << " ";
            curr = inorderSuccessor(curr);
        }
        cout << "\n";
    }
    
    bool search(int key) {
        Node* curr = root;
        while (curr) {
            if (key < curr->key) {
                if (curr->leftThread) return false;
                curr = curr->left;
            } else if (key > curr->key) {
                if (curr->rightThread) return false;
                curr = curr->right;
            } else return true;
        }
        return false;
    }
    
    void remove(int key) {
        // Complex implementation omitted for brevity
        // See full implementation in textbooks (e.g., Kruse, CLRS)
        cout << "Delete not fully implemented in this demo\n";
    }
    
    void clear() {
        // Post-order delete ignoring threads
        function del = [&](Node* n) {
            if (!n) return;
            if (!n->leftThread) del(n->left);
            if (!n->rightThread) del(n->right);
            delete n;
        };
        del(root);
        root = nullptr;
    }
};

int main() {
    ThreadedBST tbt;
    int choice, val;
    
    while (true) {
        cout << "\n1. Insert\n2. Delete\n3. Search\n4. Clear\n5. Inorder Display\n6. Exit\nChoice: ";
        cin >> choice;
        
        switch (choice) {
            case 1: cout << "Value: "; cin >> val; tbt.insert(val); break;
            case 2: cout << "Value: "; cin >> val; tbt.remove(val); break;
            case 3: cout << "Value: "; cin >> val; 
                    cout << (tbt.search(val) ? "Found" : "Not Found") << "\n"; break;
            case 4: tbt.clear(); cout << "Tree cleared\n"; break;
            case 5: cout << "Inorder: "; tbt.inorder(); break;
            case 6: return 0;
            default: cout << "Invalid\n";
        }
    }
}

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

1. Insert
2. Delete
3. Search
4. Clear
5. Inorder Display
6. Exit
Choice: 1
Value: 10
...
Choice: 5
Inorder: 3 4 5 6 7 10

Comparison

When to Use

• Frequent Inorder Traversals (Multiple Passes)
• Memory-Constrained Environments (Embedded Systems)
• When Recursion/Stack Not Available
• Database Index Structures (Some Variants)

Drawbacks

• Insert/Delete Complex (Thread Maintenance)
• Extra Memory per Node (2 Booleans)
• Not Cache-Friendly (Pointer Chasing)
• Concurrency Difficult

C++ Program: Duality Transformation of Line and Point (Point-Line Duality)

C++ Program: Find All Forward Edges in a Directed Graph (DFS Classification)