สร้างต้นไม้แบบ Mirror จาก Binary Tree ในภาษา C++

บทนำ

ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีการสร้างต้นไม้แบบ Mirror (Mirror Tree) จาก Binary Tree ที่กำหนดให้ Mirror Tree คือต้นไม้ที่โครงสร้างเป็นสะท้อนของต้นไม้ต้นฉบับ โดยการสลับตำแหน่งของโหนดลูกซ้ายและขวาในทุกระดับ

ขั้นตอนการแก้ปัญหา

1. สร้างโครงสร้างโหนด (struct Node) สำหรับ Binary Tree
2. สร้าง Binary Tree ด้วยข้อมูลตัวอย่าง
3. เขียนฟังก์ชันแบบ Recursive เพื่อแปลงต้นไม้เป็น Mirror Tree
4. พิมพ์ผลลัพธ์เพื่อตรวจสอบ

รายละเอียดการทำงาน

หลักการคือการทำ Recursive ไปยังโหนดลูกซ้ายและขวา จากนั้นสลับตัวชี้ (pointer) ของ left และ right ไปกัน ทำซ้ำจนครบทุกโหนด

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

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void convertTreeToItsMirror(struct Node* node) {
    if (node == NULL) {
        return;
    } else {
        struct Node* temp;
        convertTreeToItsMirror(node->left);
        convertTreeToItsMirror(node->right);
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}

void printTree(struct Node* node) {
    if (node == NULL) {
        return;
    }
    printTree(node->left);
    cout << node->data << " ";
    printTree(node->right);
}

int main() {
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    cout << "Tree: ";
    printTree(root);
    cout << endl;
    convertTreeToItsMirror(root);
    cout << "Mirror of the Tree: ";
    printTree(root);
    cout << endl;
    return 0;
}

ผลลัพธ์

Tree: 4 2 5 1 3
Mirror of the Tree: 3 1 5 2 4

สรุป

การสร้าง Mirror Tree ทำได้ง่ายด้วยการ Recursive และการสลับ pointer ของโหนดลูกซ้าย-ขวา หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็น