Cài đặt Threaded Binary Tree (Cây nhị phân luồng) trong C++

Threaded Binary Tree là cây nhị phân nơi các con trỏ NULL (rỗng) được tận dụng để trỏ đến **tiên nhiệm (inorder predecessor)** hoặc **kế nhiệm (inorder successor)**. Cho phép duyệt inorder không dùng stack, không đệ quy — tiết kiệm bộ nhớ và nhanh hơn.

Hai loại

Cấu trúc nút

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

Thao tác cốt lõi

1. Chèn (Insert) - Double Threaded

void insert(Node*& root, int key) {
    Node *parent = nullptr, *curr = root;
    while (curr) {
        parent = curr;
        if (key < curr->key) {
            if (curr->leftThread) break;
            curr = curr->left;
        } else if (key > curr->key) {
            if (curr->rightThread) break;
            curr = curr->right;
        } else return; // Đã tồn tại
    }
    
    Node* newNode = new Node(key);
    if (!parent) { root = newNode; return; }
    
    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. Tìm kế nhiệm Inorder (Inorder Successor)

Node* inorderSuccessor(Node* node) {
    if (node->rightThread) return node->right; // Luồng trực tiếp
    // Khác: đi xuống con phải, rồi đi trái nhất
    Node* curr = node->right;
    while (!curr->leftThread) curr = curr->left;
    return curr;
}

3. Duyệt Inorder không Stack/Đệ quy

void inorderTraversal(Node* root) {
    if (!root) return;
    // Tìm nút trái nhất
    Node* curr = root;
    while (!curr->leftThread) curr = curr->left;
    
    while (curr) {
        cout << curr->key << ' ';
        curr = inorderSuccessor(curr);
    }
    cout << '\n';
}

4. Xóa (Delete) - Phức tạp hơn do phải cập nhật thread

3 trường hợp: nút lá, 1 con, 2 con. Cần cập nhật thread của predecessor/successor. (Code đầy đủ rất dài — xem tài liệu chuyên sâu).

Chương trình hoàn chỉnh (Double Threaded, Insert + Inorder)

#include <iostream>
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;
    
    Node* leftMost(Node* node) {
        while (node && !node->leftThread) node = node->left;
        return node;
    }
    
public:
    ThreadedBST() : root(nullptr) {}
    
    void insert(int key) {
        if (!root) { root = new Node(key); return; }
        
        Node *parent = nullptr, *curr = root;
        while (curr) {
            parent = curr;
            if (key < curr->key) {
                if (curr->leftThread) break;
                curr = curr->left;
            } else if (key > curr->key) {
                if (curr->rightThread) break;
                curr = curr->right;
            } else return;
        }
        
        Node* n = new Node(key);
        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;
        }
    }
    
    void inorder() const {
        Node* curr = leftMost(root);
        while (curr) {
            cout << curr->key << ' ';
            if (curr->rightThread) curr = curr->right;
            else curr = leftMost(curr->right);
        }
        cout << '\n';
    }
    
    bool search(int key) const {
        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;
    }
};

int main() {
    ThreadedBST tbt;
    int keys[] = {10, 7, 6, 4, 5, 3};
    for (int k : keys) tbt.insert(k);
    
    cout << "Inorder traversal: ";
    tbt.inorder(); // 3 4 5 6 7 10
    
    cout << "Search 7: " << (tbt.search(7) ? "Found" : "Not found") << '\n';
    cout << "Search 1: " << (tbt.search(1) ? "Found" : "Not found") << '\n';
    
    return 0;
}

Kết quả

Inorder traversal: 3 4 5 6 7 10
Search 7: Found
Search 1: Not found

So sánh

Ứng dụng

• Hệ thống nhúng (embedded) với RAM hạn chế, không muốn dùng stack/đệ quy.
• Duyệt lặp lại nhiều lần trên cây không thay đổi thường xuyên.
• Cơ sở dữ liệu chỉ mục (database index)旧版本.

Threaded Binary Tree là kỹ thuật cổ điển nhưng vẫn có giá trị trong môi trường hạn chế tài nguyên và hệ thống real-time.