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))