โปรแกรมหาผลรวมโหนดภาพสะท้อนใน Complete Binary Tree แบบ Inorder C++

ภาพรวมปัญหา

โปรแกรมนี้หาผลรวมของโหนดในซับทรีซ้ายกับโหนดภาพสะท้อน (Mirror Image) ในซับทรีขวาของ Complete Binary Tree โดยท่องแบบ Inorder

นิยามสำคัญ

• Complete Binary Tree: ทุกระดับเต็มยกเว้นระดับสุดท้ายที่เต็มจากซ้ายไปขวา
• Mirror Image Nodes: โหนดที่อยู่ตำแหน่งสมมาตรกันผ่านแกนกลาง (Root)
• Inorder Traversal: Left → Root → Right

ตัวอย่างภาพประกอบ

        1           ← Root (Level 0)
       / \
      7   2         ← Level 1: Mirror pairs (7,2)
     / \ / \
    5  8 9  4       ← Level 2: Mirror pairs (5,4), (8,9)

Inorder of Left Subtree (root=7): 5 → 7 → 8
Mirror pairs: (5,4), (7,2), (8,9)
Sums: 5+4=9, 7+2=9, 8+9=17
Root self-pair: 1+1=2

อัลกอริทึม

1. ท่อง Inorder ซับทรีซ้าย (Left Subtree)
2. พร้อมกันท่อง Mirror ในซับทรีขวา (Right Subtree) แบบ Mirror Inorder: Right → Root → Left
3. ที่แต่ละคู่ ให้บวกค่าทั้งสองโหนด
4. สุดท้ายบวก Root กับตัวเอง (Root+Root)

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

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

// ท่อง Inorder ซับทรีซ้าย และ Mirror Inorder ซับทรีขวา พร้อมกัน
void printMirrorSum(Node* leftNode, Node* rightNode) {
    if (!leftNode || !rightNode) return;
    
    // Inorder: Left → Root → Right
    // Mirror Inorder: Right → Root → Left
    
    // 1. Traverse Left's Left และ Right's Right
    printMirrorSum(leftNode->left, rightNode->right);
    
    // 2. Process Current Pair
    cout << (leftNode->data + rightNode->data) << " ";
    
    // 3. Traverse Left's Right และ Right's Left
    printMirrorSum(leftNode->right, rightNode->left);
}

int main() {
    // สร้างต้นไม้จากตัวอย่าง
    Node* root = new Node(1);
    root->left = new Node(7);
    root->right = new Node(2);
    root->left->left = new Node(5);
    root->left->right = new Node(8);
    root->right->left = new Node(9);
    root->right->right = new Node(4);
    
    cout << "Mirror Image Node Sums (Inorder of Left Subtree):\n";
    printMirrorSum(root->left, root->right);
    cout << endl;
    
    // Root กับตัวเอง
    cout << "Root self-pair: " << (root->data + root->data) << endl;
    
    return 0;
}

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

Mirror Image Node Sums (Inorder of Left Subtree):
9 9 17 
Root self-pair: 2

การทำงานขั้นตอน (Step-by-step)

โค้ดเวอร์ชันครบถ้วน (รองรับต้นไม้ไม่สมบูรณ์)

void printMirrorSumSafe(Node* leftNode, Node* rightNode) {
    if (!leftNode && !rightNode) return;
    if (!leftNode || !rightNode) {
        // หนึ่งข้างไม่มีโหนด - ปรับตามต้องการ (skip หรือ error)
        return;
    }
    
    printMirrorSumSafe(leftNode->left, rightNode->right);
    cout << (leftNode->data + rightNode->data) << " ";
    printMirrorSumSafe(leftNode->right, rightNode->left);
}

// สำหรับ Complete Binary Tree ที่สมบูรณ์ ไม่ต้องตรวจสอบ NULL
// เพราะทุกโหนดใน Left Subtree จะมี Mirror ใน Right Subtree

ความซับซ้อนของอัลกอริทึม

• เวลา: O(N) โดย N = จำนวนโหนดในซับทรีซ้าย (≈ N/2)
• พื้นที่: O(H) โดย H = ความสูงของต้นไม้ (Recursion Stack)
• สำหรับ Complete Binary Tree: H = O(log N)

ความแตกต่าง: Complete vs Perfect vs Full Binary Tree

ประยุกต์ใช้

• การตรวจสอบ Symmetry ของต้นไม้
• การบีบอัดรูปภาพ (Image Compression - Quadtree)
• Computer Graphics - Reflection Effects
• Data Structure Validation

ข้อควรระวัง

• โค้ดสมมติว่าเป็น Complete Binary Tree ที่สมมาตร
• ถ้าต้นไม้ไม่สมมาตร ต้องเพิ่ม Null Checks
• Inorder ของซับทรีซ้าย ตรงกับ Mirror Inorder ของซับทรีขวา
• Root ไม่ได้อยู่ใน Inorder ของซับทรี จึงต้องบวกแยกต่างหาก