C++에서 대괄호가 있는 문자열에 대한 이진 트리

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 C++에서 이진 트리를 대괄호가 있는 문자열로 변환하는 프로그램을 만드는 것입니다.

이진 트리의 값은 정수이며 선주문 순회 방식으로 프로그램에 제공됩니다. 문자열은 정수와 괄호()만 포함해야 하며 최적화되어야 합니다. 즉, 모든 빈 쌍을 제거해야 합니다.

이진 트리 각 노드가 최대 2개의 자식을 가질 수 있는 특별한 조건을 가진 트리입니다.

이진 트리의 예 -

선주문 순회 :[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))

이제 문제를 해결하고 이진 트리의 선주문 순회를 수행하고 필요한 곳에 대괄호를 배치합니다. 또한 여분의 중괄호 쌍을 제거해야 합니다. 이를 위해 대괄호를 배치할 함수에 대한 재귀 호출을 사용합니다.

노드를 인쇄하고 노드, 즉 리프 노드에 대해 자식이 남지 않을 때까지 문장으로 노드의 자식 모두에 대해 재귀 함수를 호출합니다.

노드의 자식 노드에 대한 함수를 호출하는 동안 다음 4가지 경우 중 하나가 발생합니다. -

사례 1 − 노드에 두 개의 자식 노드가 모두 있는 경우. 두 자식 모두에 대괄호를 배치하고 해당 값을 대괄호 안에 넣고 자식 노드가 있는 경우 해당 노드를 호출합니다.

예 - 루트 노드에 대한 위의 예에서 두 자식 노드가 모두 있는 4, 4(1)(9).

사례 2 − 노드에 왼쪽 자식만 있는 경우. 오른쪽 자식이 없기 때문에 왼쪽 자식을 대괄호에 넣습니다. 대괄호는 제거됩니다. 그리고 왼쪽 자식의 하위 트리가 있는 경우에만 호출됩니다.

예 - 왼쪽 자식 노드만 존재하는 값이 1인 노드에 대한 위의 예에서 4(1(8()()))(9).

사례 3 - 노드에 오른쪽 자식만 있는 경우. 우리는 왼쪽 자식을 위해 빈 괄호를 넣을 것입니다. 그리고 오른쪽 자식의 값이 배치되고 하위 트리가 있으면 호출됩니다.

사례 4 − 노드에 자식이 없는 경우(리프 노드). 대괄호는 넣지 않고 값만 넣습니다.

예 - 자식이 없는 값이 5인 노드의 경우 위의 예에서 4(1(8(3)))(9(2)(5()())).

이진 트리를 대괄호가 있는 문자열로 변환하는 프로그램

//이진 트리를 대괄호가 있는 문자열로 변환하는 프로그램

예시

#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;
}

출력

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