แปลง Binary Tree เป็น String พร้อมวงเล็บใน C++

ในโจทย์นี้ เราได้รับ binary tree มาหนึ่งต้น งานของเราคือเขียนโปรแกรมแปลง binary tree ให้เป็น string ที่มีวงเล็บใน C++

ค่าของ binary tree เป็นจำนวนเต็ม และจะถูกส่งเข้าโปรแกรมในรูปแบบ preorder traversal String ที่ได้ควรประกอบด้วยตัวเลขและวงเล็บ () เท่านั้น และต้องเป็นรูปแบบที่เหมาะสมที่สุด คือ ต้องกำจัดคู่วงเล็บว่างเปล่าทั้งหมด

Binary Tree คือต้นไม้ที่มีเงื่อนไขพิเศษคือ แต่ละโหนดสามารถมีลูกได้สูงสุดสองโหนด

ตัวอย่าง Binary Tree

Preorder traversal: [4, 1, 8, 3, 9, 2, 5]

ตัวอย่างปัญหา

อินพุต

preorder: [4, 1, 8, 3, 9, 2, 5]

เอาต์พุต

คำอธิบาย

Root -> 4()() -> 4(1()())(9) -> 4(1(8()())())(9) -> 4(1(8(3)())())(9) -> 4(1(8(3)())())(9(2)(5))

หลังจากกำจัดวงเล็บว่างทั้งหมด:

4(1(8(3)))(9(2)(5))

ตอนนี้มาแก้ปัญหานี้กัน เราจะทำ preorder traversal ของ binary tree และวางวงเล็บที่จำเป็น พร้อมทั้งกำจัดคู่วงเล็บที่เกินออกไป โดยใช้การเรียกฟังก์ชันแบบ recursive

เราจะพิมพ์โหนด และเรียกฟังก์ชัน recursive สำหรับลูกทั้งสองของโหนด จนกว่าจะไม่มีลูกเหลือ (leaf node)

ขณะเรียกฟังก์ชันสำหรับลูกของโหนด เราจะเจอ 4 กรณี ดังนี้:

กรณีที่ 1 - โหนดมีลูกทั้งสองข้าง เราจะวางวงเล็บให้ทั้งสองลูก วางค่าของลูกไว้ในวงเล็บ และเรียกฟังก์ชันสำหรับลูกของลูก (ถ้ามี)

ตัวอย่าง - จากตัวอย่างข้างต้น สำหรับรูทโหนด 4 ที่มีลูกทั้งคู่: 4(1)(9)

กรณีที่ 2 - โหนดมีลูกซ้ายอย่างเดียว เราจะวางลูกซ้ายในวงเล็บ เนื่องจากไม่มีลูกขวา วงเล็บขวาจะถูกกำจัด และเรียกเฉพาะ subtree ของลูกซ้าย (ถ้ามี)

ตัวอย่าง - จากตัวอย่างข้างต้น สำหรับโหนดค่า 1 ที่มีลูกซ้ายอย่างเดียว: 4(1(8()()))(9)

กรณีที่ 3 - โหนดมีลูกขวาเพียงอย่างเดียว เราจะวางวงเล็บว่างสำหรับลูกซ้าย และวางค่าลูกขวา พร้อมเรียก sub-tree ของลูกขวา (ถ้ามี)

กรณีที่ 4 - โหนดไม่มีลูก (leaf node) เราจะไม่วางวงเล็บ แค่พิมพ์ค่าเท่านั้น

ตัวอย่าง - จากตัวอย่างข้างต้น สำหรับโหนดค่า 5 ที่ไม่มีลูก: 4(1(8(3)))(9(2)(5()()))

โปรแกรมแปลง Binary Tree เป็น String พร้อมวงเล็บ

// โปรแกรมแปลง Binary Tree เป็น String พร้อมวงเล็บ

ตัวอย่าง

#include <iostream>
using namespace std;

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

Node* insertNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

void ConvertBinaryTreeToString(Node* root, string& str) {
    if (root == NULL)
        return;
    str.push_back(root->data + '0');
    if (!root->left && !root->right)
        return;
    str.push_back('(');
    ConvertBinaryTreeToString(root->left, str);
    str.push_back(')');
    if (root->right) {
        str.push_back('(');
        ConvertBinaryTreeToString(root->right, str);
        str.push_back(')');
    }
}

int main() {
    struct Node* root = insertNode(4);
    root->left = insertNode(1);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->left->left = insertNode(3);
    root->right->left = insertNode(2);
    root->right->right = insertNode(5);
    string binaryTreeString = "";
    ConvertBinaryTreeToString(root, binaryTreeString);
    cout << "The string with preorder traversal of binary tree with brackets is: " << binaryTreeString;
    return 0;
}

ผลลัพธ์

The string with preorder traversal of binary tree with brackets is: 4(1(8(3)))(9(2)(5))