Double Tree (ต้นไม้คู่) ในภาษา C++ พร้อมตัวอย่าง

บทนำ

Double Tree คือการแปลง Binary Tree ให้แต่ละโหนดมีโหนดลูกซ้ายใหม่ที่มีค่าเท่ากับโหนดปัจจุบัน และโหนดลูกซ้ายเดิมจะกลายเป็นลูกซ้ายของโหนดใหม่นั้น

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

1. สร้างคลาสโหนด (node class)
2. สร้างต้นไม้ด้วยข้อมูลตัวอย่าง
3. เขียนฟังก์ชัน Recursive เพื่อทำ Double Tree
4. พิมพ์ต้นไม้ก่อนและหลังการแปลง

รายละเอียดอัลกอริทึม

ฟังก์ชัน doubleTree() จะ:

• Recursive ไปยังลูกซ้ายและขวาก่อน (Post-order)
• เก็บ pointer ของลูกซ้ายเดิมไว้
• สร้างโหนดใหม่ที่มีค่าเท่ากับโหนดปัจจุบัน
• ตั้งโหนดใหม่เป็นลูกซ้าย และลูกซ้ายเดิมเป็นลูกซ้ายของโหนดใหม่

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

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

class node {
public:
    int data;
    node* left;
    node* right;
};

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

void doubleTree(node* Node) {
    node* oldLeft;
    if (Node == NULL) return;
    doubleTree(Node->left);
    doubleTree(Node->right);
    oldLeft = Node->left;
    Node->left = newNode(Node->data);
    Node->left->left = oldLeft;
}

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

int main() {
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    cout << "Original Tree" << endl;
    printTree(root);
    cout << endl;
    doubleTree(root);
    cout << "Double Tree" << endl;
    printTree(root);
    cout << endl;
    return 0;
}

ผลลัพธ์

Original Tree: 2 1 3
Double Tree: 2 2 1 1 3 3

สรุป

Double Tree เพิ่มจำนวนโหนดเป็นสองเท่าโดยการสร้างโหนดลูกซ้ายใหม่สำหรับทุกโหนด แนวคิดนี้น่าสนใจสำหรับการศึกษาโครงสร้างข้อมูลต้นไม้