Chuyển đổi cây nhị phân thành cây nhị phân luồn (Threaded Binary Tree) dùng Queue trong C++

Cây nhị phân luồn (threaded binary tree) là cây nhị phân nơi các con trỏ NULL của nút lá được trỏ đến tiền nhiệm hoặc kế nhiệm theo thứ tự inorder, giúp duyệt cây không cần đệ quy hay stack.

Phương pháp sử dụng Queue:

1. Duyệt inorder cây gốc, đưa các nút vào queue theo thứ tự inorder.
2. Duyệt lại cây inorder, mỗi khi gặp nút có con trỏ phải NULL, gán con trỏ phải = phần tử đầu queue (keo nhiệm inorder) và đánh dấu isThreaded = true.

Ví dụ minh họa (C++)

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

struct Node {
    int key;
    Node *left, *right;
    bool isThreaded;
};

// Đưa các nút vào queue theo inorder
void convert_queue(Node* root, queue<Node*>* q) {
    if (!root) return;
    if (root->left) convert_queue(root->left, q);
    q->push(root);
    if (root->right) convert_queue(root->right, q);
}

// Tạo luồn (thread) từ queue
void create_threadedtree(Node* root, queue<Node*>* q) {
    if (!root) return;
    if (root->left) create_threadedtree(root->left, q);
    q->pop(); // bỏ nút hiện tại khỏi queue
    if (root->right) create_threadedtree(root->right, q);
    else {
        root->right = q->front(); // trỏ đến kế nhiệm inorder
        root->isThreaded = true;
    }
}

void createThreaded(Node* root) {
    queue<Node*> q;
    convert_queue(root, &q);
    create_threadedtree(root, &q);
}

// Tìm nút trái nhất
Node* leftMost(Node* root) {
    while (root && root->left) root = root->left;
    return root;
}

// Duyệt inorder trên cây luồn
void inOrder(Node* root) {
    if (!root) return;
    Node* cur = leftMost(root);
    while (cur) {
        cout << cur->key << " ";
        if (cur->isThreaded) cur = cur->right;
        else cur = leftMost(cur->right);
    }
}

Node* newNode(int key) {
    Node* temp = new Node();
    temp->key = key;
    temp->left = temp->right = nullptr;
    temp->isThreaded = false;
    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 << "Duyet inorder cay luon: ";
    inOrder(root);
    return 0;
}

Kết quả

Duyet inorder cay luon: 4 2 5 1 6 3 7