Duyệt Inorder của cây nhị phân luồn (Threaded Binary Tree) trong C++

Cây nhị phân luồn (Threaded Binary Tree) tận dụng các con trỏ NULL của nút lá để trỏ đến tiền nhiệm/hậu nhiệm theo thứ tự inorder, giúp duyệt cây không cần stack hay đệ quy.

Cây luồn đầy đủ (fully threaded): mỗi nút có 5 trường: cờ trái, con trỏ trái, dữ liệu, con trỏ phải, cờ phải. Cờ = true nghĩa là con trỏ là luồn (thread), false là con trỏ cây thông thường.

Thuật toán duyệt Inorder

inorder():
    temp = root
    lặp vô tận:
        p = temp
        temp = right của temp
        nếu cờ phải của p là false (là con trỏ cây):
            بينما cờ trái của temp không phải luồn:
                temp = left của temp
        nếu temp == root: break
        in dữ liệu của temp

Ví dụ mã nguồn

#include <iostream>
#define MAX_VALUE 65536
using namespace std;

class Node {
public:
    int key;
    Node *left, *right;
    bool leftThread, rightThread;
};

class ThreadedBinaryTree {
private:
    Node *root;
public:
    ThreadedBinaryTree() {
        root = new Node();
        root->right = root->left = root;
        root->leftThread = true;
        root->key = MAX_VALUE;
    }
    
    void chen(int key) {
        Node *p = root;
        for (;;) {
            if (p->key < key) {
                if (p->rightThread) break;
                p = p->right;
            } else if (p->key > key) {
                if (p->leftThread) break;
                p = p->left;
            } else return;
        }
        Node *temp = new Node();
        temp->key = key;
        temp->leftThread = temp->rightThread = true;
        if (p->key < key) {
            temp->right = p->right;
            temp->left = p;
            p->right = temp;
            p->rightThread = false;
        } else {
            temp->right = p;
            temp->left = p->left;
            p->left = temp;
            p->leftThread = false;
        }
    }
    
    void inorder() {
        Node *temp = root, *p;
        for (;;) {
            p = temp;
            temp = temp->right;
            if (!p->rightThread) {
                while (!temp->leftThread)
                    temp = temp->left;
            }
            if (temp == root) break;
            cout << temp->key << " ";
        }
        cout << endl;
    }
};

int main() {
    ThreadedBinaryTree tbt;
    cout << "Cây nhị phân luồn\n";
    tbt.chen(56);
    tbt.chen(23);
    tbt.chen(89);
    tbt.chen(85);
    tbt.chen(20);
    tbt.chen(30);
    tbt.chen(12);
    tbt.inorder();
    return 0;
}

Kết quả chạy chương trình

Cây nhị phân luồn
12 20 23 30 56 85 89