Chuyển Biểu Thức Ba Ngòi (Ternary) Thành Cây Nhị Phân Trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận chương trình chuyển biểu thức ba ngòi (ternary) thành cây nhị phân.

Cho một biểu thức ba ngòi. Nhiệm vụ là chuyển biểu thức đó thành dạng cây nhị phân tùy thuộc vào các đường đi (lựa chọn) có thể.

Ví Dụ

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

// Cấu trúc nút cây
struct Node {
    char data;
    Node *left, *right;
};

// Tạo nút mới
Node* newNode(char Data) {
    Node* new_node = new Node;
    new_node->data = Data;
    new_node->left = new_node->right = NULL;
    return new_node;
}

// Chuyển biểu thức ternary thành cây nhị phân
Node* convertExpression(string str, int& i) {
    // Lưu ký tự hiện tại
    Node* root = newNode(str[i]);
    // Nếu là ký tự cuối, trả về base case
    if (i == str.length() - 1)
        return root;
    i++;
    // Nếu ký tự tiếp theo là '?', có cây con cho nút hiện tại
    if (str[i] == '?') {
        // Bỏ qua '?'
        i++;
        root->left = convertExpression(str, i);
        // Bỏ qua ':'
        i++;
        root->right = convertExpression(str, i);
        return root;
    }
    else
        return root;
}

// In cây nhị phân (preorder)
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;
}

Đầu Ra

a b c d e