Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là tạo một chương trình sẽ chuyển đổi cây nhị phân thành chuỗi có dấu ngoặc trong C ++.
Các giá trị của cây nhị phân là các số nguyên và nó sẽ được cung cấp cho chương trình theo cách duyệt qua được đặt hàng trước. Chuỗi chỉ nên chứa các số nguyên và dấu ngoặc đơn (), cũng như nó phải được tối ưu hóa, tức là tất cả các cặp trống phải được loại bỏ.
Cây nhị phân là một cây có điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con.
Ví dụ về cây nhị phân -
Đặt hàng trước truyền tải:[4, 1, 8, 3, 9, 2, 5]
Hãy lấy một ví dụ để hiểu vấ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 dấu ngoặc đơn trống,
4(1(8(3)))(9(2)(5))
Bây giờ, chúng ta hãy giải quyết vấn đề, chúng ta sẽ thực hiện việc duyệt qua đặt hàng trước của cây nhị phân và chúng ta sẽ đặt dấu ngoặc ở bất cứ nơi nào cần thiết. Ngoài ra, chúng ta sẽ phải loại bỏ các cặp niềng răng thừa. Đối với điều này, chúng tôi sẽ sử dụng lệnh gọi đệ quy tới một hàm sẽ đặt dấu ngoặc.
chúng ta sẽ in một nút và gọi hàm đệ quy cho cả nút con của nút với các câu cho đến khi không còn nút con nào cho nút tức là nút lá.
Trong 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ó mặt cả hai nút con. Chúng tôi sẽ đặt dấu ngoặc cho cả con và đặt giá trị của chúng bên trong dấu ngoặc và 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 bên trái. Chúng ta sẽ đặt con bên trái vào trong ngoặc, vì không có con bên phải nào có mặt thì dấu ngoặc của nó sẽ bị loại. Và chỉ những cây con bên trái của con mới được gọ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 bên trái, 4 (1 (8 () ())) (9).
Trường hợp 3 - Khi nút chỉ có nút con bên phải. Chúng ta sẽ đặt một dấu ngoặc trống cho con bên trái. Và giá trị của con bên 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ó con (nút lá). Chúng tôi sẽ không đặt bất kỳ dấu ngoặc nào và chỉ đặt giá trị.
Ví dụ - từ ví dụ trên cho các nút có giá trị 5 mà không có con nào hiện diện, 4 (1 (8 (3))) (9 (2) (5 () ())).
Chương trình chuyển cây nhị phân thành chuỗi có dấu ngoặc nhọn
// Chương trình chuyển cây nhị phân thành chuỗi có dấu ngoặc nhọn
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<<"The string with preorder traversal of binary tree with brackets is: "<<binaryTreeString;
} Đầu ra
The string with preorder traversal of binary tree with brackets is: 4(1(8(3)))(9(2)(5))