C++での順序どおりの完全なバイナリツリーのミラーイメージノードの合計

この問題では、完全な二分木が与えられます。私たちのタスクは、完全な二分木の鏡像ノードの合計を順番に見つけるプログラムを作成することです。

ここでは、左側の太陽の木の順番の走査を見つける必要があります。次に、ノードごとに、それを使用して鏡像を追加します。これは、左側の葉ノードをトラバースする場合、右側の葉ノードの値を追加することを意味します。鏡像ノードなので。

いくつかの重要な定義

完全な二分木 は、最後のレベルを除くすべてのレベルのノード数が最も多い二分木です。

順序のないトラバーサル は、左側のサブツリーが最初に訪問され、ルートが訪問され、右側のサブツリーが訪問されるツリートラバーサル手法です。

問題を理解するために例を見てみましょう

入力

出力 − 9 9 17 2

説明 −左側のサブツリーの順序付けられた走査は5-7-8-1です。

すべてのノードを追加すると、画像がミラーリングされます。

5 + 4 = 9
7 + 2 = 9
8 + 9 = 17
1 + 1 = 2

この問題を解決するために、順序トラバーサルを使用してバイナリツリーをトラバースします。 2つのノードを使用します。1つは左側のサブツリーをトラバースし、もう1つはノードのミラーにアクセスします。たとえば、左側のサブツリーのルートノードがあり、そのサブツリーのミラーイメージをトラバースするミラールートがあります。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
typedef struct node {
   int data;
   struct node* left;
   struct node* right;
   node(int d){
      data = d;
      left = NULL;
      right = NULL;
   }
} Node;
void printMirrorSum(Node* root, Node* rootMirror){
   if (root->left == NULL && rootMirror->right == NULL)
      return;
   printMirrorSum(root->left, rootMirror->right);
   cout<<(root->left->data + rootMirror->right->data)<<endl;
   printMirrorSum(root->right, rootMirror->left);
}
int main(){
   Node* root = new Node(1);
   root->left = new Node(7);
   root->right = new Node(2);
   root->left->left = new Node(5);
   root->left->right = new Node(8);
   root->right->left = new Node(9);
   root->right->right = new Node(4);
   cout<<"Sum of node and mirror image nodes are :\n";
   printMirrorSum(root, root);
   if (root)
      cout<<(root->data + root->data);
   return 0;
}

出力

Sum of node and mirror image nodes are :
9
9
17
2