C++で指定された順序トラバーサルから特別な二分木を構築します

例

入力

int arr[] = {10, 20, 28, 40, 32, 31, 30}

出力

与えられた順序トラバーサルで構築される特別な二分木を以下に示します-

説明

we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 28, 40, 32, 31, 30

入力

int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35}

出力

The special binary tree which will be constructed with the given inorder
traversal is given below −

説明

we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 25, 28, 40, 32, 31, 30, 35.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、ルートノードとして最大要素を使用して、指定された配列から特別なバイナリツリーを構築します。その左側の要素は左側のサブツリーの一部になり、右側の要素は右側のサブツリーの一部になります。このプロセスは、ツリーを構築するために再帰的に実行されます。

• インオーダートラバーサルを含む入力配列としてarr[]を取ります。

• 関数new_node（int data）は、左右の子をNULLとして持つノードを作成します。

• 関数total（int arr []、int first、int last）は、その要素のインデックスを返します。

• 最高=arr[first]、最低=firstを取ります。

• 最初の+1インデックスから最後までトラバースし、要素arr [i]が最高よりも大きい場合は、そのインデックスを最低に格納し、最高に更新します。

• forループの最後に、lowestにはhighest要素のインデックスが含まれます。

• 関数create_tree（int arr []、int first、int last）は、arr[]から特別なバイナリツリーを再帰的に構築します。

• 最初>最後の場合、ツリーは不可能であるため、NULLを返します。

• temp =total（arr、first、last）を使用して、配列の最大値としてtempを取得します。

• データとしてtempを使用してノードを作成し、ツリーのルートノードを指すポインタの親ポイントを作成します。

• first ==lastの場合、ツリーにはノードが1つだけあります。親を返します。

• parent-> left =create_tree（arr、first、temp − 1）;

  を再帰的に計算します

• そして、parent-> right =create_tree（arr、temp + 1、last）。

• 最後に親を返します。

• 関数Inorder_traversal（tree_node * node）は、上で生成されたツリーのインオーダートラバーサルを出力します。

• ノードがNULLの場合、何も返しません。それ以外の場合は、最初にInorder_traversal（node-> left）を使用して左のサブツリーを出力します。

• 次に、現在のノードを印刷します。

• 次に、Inorder_traversal（node-> right）を使用して右側のサブツリーを出力します。

例

#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node{
   public:
   int data;
   tree_node* left;
   tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree (int arr[], int first, int last){
   if(first > last){
      return NULL;
   }
   int temp = total(arr, first, last);
   tree_node *parent = new_node(arr[temp]);
   if(first == last){
      return parent;
   }
   parent−>left = create_tree(arr, first, temp − 1);
   parent−>right = create_tree(arr, temp + 1, last);
   return parent;
}
int total(int arr[], int first, int last){
   int highest = arr[first];
   int lowest = first;
   for(int i = first + 1; i <= last; i++){
      if(arr[i] > highest){
         highest = arr[i];
         lowest = i;
      }
   }
   return lowest;
}
tree_node* new_node (int data){
   tree_node* newNode = new tree_node();
   newNode−>data = data;
   newNode−>left = NULL;
   newNode−>right = NULL;
   return newNode;
}
void Inorder_traversal(tree_node* node){
   if (node == NULL){
      return;
   }
   Inorder_traversal(node−>left);
   cout<<node−>data<<" ";
   Inorder_traversal (node−>right);
}
int main(){
   int arr[] = {10, 20, 28, 40, 32, 31, 30};
   int size = sizeof(arr)/sizeof(arr[0]);
   tree_node *root = create_tree(arr, 0, size − 1);
   cout<<"Construct Special Binary Tree from given Inorder traversal are: "<<"\n";
   Inorder_traversal(root);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Construct Special Binary Tree from given Inorder traversal are:
10, 20, 28, 40, 32, 31, 30