Chuyển đổi cây nhị phân thành chuỗi với ngoặc trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân. Nhiệm vụ là tạo một chương trình chuyển đổi cây nhị phân thành chuỗi có ngoặc trong C++.

Các giá trị của cây nhị phân là số nguyên và sẽ được cung cấp cho chương trình theo cách duyệt tiền tự (preorder). Chuỗi kết quả chỉ chứa số nguyên và dấu ngoặc (), đồng thời phải được tối ưu hóa tức là loại bỏ tất cả các cặp ngoặc rỗng.

Cây nhị phân là cây có điều kiện đặc biệt: mỗi nút có tối đa hai nút con.

Ví dụ về cây nhị phân

Duyệt tiền tự: [4, 1, 8, 3, 9, 2, 5]

Hãy xem ví dụ để hiểu bài toán

Đầu vào

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

Đầu ra

Giải thích

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

Loại bỏ tất cả các cặp ngoặc rỗng,

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

Bây giờ, hãy giải quyết bài toán. Chúng ta sẽ thực hiện duyệt tiền tự của cây nhị phân và đặt ngoặc ở những nơi cần thiết. Cũng phải loại bỏ các cặp ngoặc thừa. Để làm điều này, chúng ta sẽ sử dụng gọi đệ quy đến một hàm sẽ đặt ngoặc.

Chúng ta sẽ in một nút và gọi hàm đệ quy cho cả hai nút con của nút đó cho đến khi không còn nút con nào cho một nút, tức là nút lá.

Khi gọi hàm cho các nút con của một nút, chúng ta sẽ gặp một trong 4 trường hợp sau:

Trường hợp 1 - Khi nút có cả hai nút con. Chúng ta sẽ đặt ngoặc cho cả hai nút con và đặt giá trị của chúng bên trong ngoặc, sau đó gọi các nút con của chúng nếu có.

Ví dụ - từ ví dụ trên cho nút gốc 4 nơi có cả hai nút con, 4(1)(9).

Trường hợp 2 - Khi nút chỉ có nút con trái. Chúng ta sẽ đặt nút con trái trong ngoặc, vì không có nút con phải nên ngoặc của nó sẽ bị loại bỏ. Chỉ gọi đệ quy cho cây con trái nếu có.

Ví dụ - từ ví dụ trên cho nút có giá trị 1 nơi chỉ có nút con trái, 4(1(8()()))(9).

Trường hợp 3 - Khi nút chỉ có nút con phải. Chúng ta sẽ đặt một cặp ngoặc rỗng cho nút con trái. Và giá trị của nút con phải sẽ được đặt và các cây con của nó sẽ được gọi nếu có.

Trường hợp 4 - Khi nút không có nút con (nút lá). Chúng ta không đặt bất kỳ ngoặc nào và chỉ in giá trị.

Ví dụ - từ ví dụ trên cho các nút có giá trị 5 nơi không có nút con, 4(1(8(3)))(9(2)(5()())).

Chương trình chuyển đổi cây nhị phân thành chuỗi có ngoặc

//Chương trình chuyển đổi cây nhị phân thành chuỗi có ngoặc

Ví dụ

#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 ConveryBinaryTreeToString(Node* root, string& str){    if (root == NULL)    return;    str.push_back(root->data + '0');    if (!root->left && !root->right)    return;    str.push_back('(');    ConveryBinaryTreeToString(root->left, str);    str.push_back(')');    if (root->right) {       str.push_back('(');       ConveryBinaryTreeToString(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 = "";    ConveryBinaryTreeToString(root, binaryTreeString);    cout<<"Chuỗi với duyệt tiền tự của cây nhị phân có ngoặc là: "<<binaryTreeString; }

Đầu ra

Chuỗi với duyệt tiền tự của cây nhị phân có ngoặc là: 4(1(8(3)))(9(2)(5))