แปลง Ternary Expression เป็น Binary Tree ใน C++

ภาพรวมปัญหา

แปลง Ternary Expression (เช่น a?b?c:d:e) เป็น Binary Tree

ตัวอย่าง

Expression: "a?b?c:d:e"
Tree Structure:
       a
      / \
     b   e
    / \
   c   d

วิธีแก้ปัญหา (Recursive Parsing)

1. อ่านตัวอักษรปัจจุบันสร้างโหนด
2. ถ้าตัวถัดไปคือ '?' → มี Subtree: ข้าม '?' → Recursive สร้าง Left → ข้าม ':' → Recursive สร้าง Right
3. ถ้าไม่ใช่ '?' → เป็น Leaf Node

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

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

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

Node* newNode(char Data) {
    Node* new_node = new Node;
    new_node->data = Data;
    new_node->left = new_node->right = NULL;
    return new_node;
}

Node* convertExpression(string str, int& i) {
    Node* root = newNode(str[i]);
    if (i == str.length() - 1) return root;
    i++;
    if (str[i] == '?') {
        i++; // skip '?'
        root->left = convertExpression(str, i);
        i++; // skip ':'
        root->right = convertExpression(str, i);
        return root;
    }
    return root;
}

void display_tree(Node* root) {
    if (!root) return;
    cout << root->data << " ";
    display_tree(root->left);
    display_tree(root->right);
}

int main() {
    string expression = "a?b?c:d:e";
    int i = 0;
    Node* root = convertExpression(expression, i);
    display_tree(root);
    return 0;
}

ผลลัพธ์ (Output)

a b c d e