พิมพ์ BST Keys ในช่วงที่กำหนด ใช้พื้นที่ O(1) ด้วย Morris Traversal ใน C++

บทนำ

โจทย์: พิมพ์ Key ของ BST ที่อยู่ในช่วง [k1, k2] เรียงจากน้อยไปมาก ใช้พื้นที่ O(1) (ไม่ใช้ Stack/Queue/Recursion)

Morris Traversal (Threaded Binary Tree)

ใช้ NULL pointer ของโหนดใบชี้ไปยัง Inorder Successor แทน Stack ขั้นตอน: 1. ถ้าไม่มีลูกซ้าย → visit แล้วไปขวา 2. ถ้ามีลูกซ้าย → หา Inorder Predecessor (ขวามากสุดของลูกซ้าย) - ถ้า predecessor->right == NULL → ตั้ง thread ไป current, ไปซ้าย - ถ้า predecessor->right == current → ลบ thread, visit current, ไปขวา

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

struct node {
    int data;
    struct node *left, *right;
};

node* insertNode(int data) {
    node* temp = new node;
    temp->data = data;
    temp->right = temp->left = NULL;
    return temp;
}

void RangeTraversal(node* root, int k1, int k2) {
    if (!root) return;
    node* nodeTraversal = root;
    while (nodeTraversal) {
        if (nodeTraversal->left == NULL) {
            if (nodeTraversal->data <= k2 && nodeTraversal->data >= k1)
                cout << nodeTraversal->data << " ";
            nodeTraversal = nodeTraversal->right;
        } else {
            node* prevNode = nodeTraversal->left;
            while (prevNode->right != NULL && prevNode->right != nodeTraversal)
                prevNode = prevNode->right;
            if (prevNode->right == NULL) {
                prevNode->right = nodeTraversal;
                nodeTraversal = nodeTraversal->left;
            } else {
                prevNode->right = NULL;
                if (nodeTraversal->data <= k2 && nodeTraversal->data >= k1)
                    cout << nodeTraversal->data << " ";
                nodeTraversal = nodeTraversal->right;
            }
        }
    }
}

int main() {
    node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(2);
    root->left->left = insertNode(1);
    root->left->right = insertNode(7);
    root->right->right = insertNode(9);
    cout << "All BST keys in the given range are \t";
    RangeTraversal(root, 4, 10);
    return 0;
}

ผลลัพธ์

All BST keys in the given range are 7 6 9

คำอธิบายต้นไม้

ช่วง [4,10]: 7, 6, 9 (เรียง Inorder: 6, 7, 9 แต่ Morris Traversal พิมพ์ตามลำดับที่ visit)

สรุป

Morris Traversal ทำ Inorder Traversal ได้ O(1) Space เหมาะสำหรับระบบ Embedded หรือ Memory-constrained