C++でのプレオーダートラバーサルから完全なk-aryツリーを構築します

k-aryツリーのプレオーダートラバーサルを順番に含む配列arr[]が与えられます。目標は、そこから同じk-aryツリーを構築し、そのポストオーダートラバーサルを出力することです。完全なk-aryツリーは、ルートノードに0個またはk個の子、つまり最大でk個の子があるツリーです。

例

入力

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2

出力

プレオーダートラバーサルからの2人の子で構築される完全なk-aryツリーを以下に示します-

説明

整数値の配列、または2であるk個の子を持つツリーのプレオーダートラバーサルが与えられます。したがって、形成されたツリーは、次のルールに従って構築された3 6 1 2 1 752としてポストオーダートラバーサルを持ちます。すべてのLEFTサブツリーノードにアクセスしてから、すべてのRIGHTサブツリーノードにアクセスしてから、すべてのROOTノードにアクセスします。

入力

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3

出力

プレオーダートラバーサルからの3人の子で構築される完全なk-aryツリーを以下に示します-

説明

整数値の配列、または3であるk個の子を持つツリーのプレオーダートラバーサルが与えられます。したがって、形成されたツリーは、次のルールに従って構築された3 6 1 2 1 752としてポストオーダートラバーサルを持ちます。すべてのLEFTサブツリーノードにアクセスしてから、すべてのRIGHTサブツリーノードにアクセスしてから、すべてのROOTノードにアクセスします。

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

このアプローチでは、最初に、最初の要素をルートノードとして、指定された配列からk-aryツリーを構築します。左側のサブツリーが空の場合、右側のサブツリーも空になります。左と右のサブツリーを再帰的に呼び出し、それらをリンクします。ポストオーダートラバーサルでは、左のサブツリー、右のサブツリーの順に取得し、ノードの重みを出力します。

• postorder（root-> left）

  を呼び出す

• postorder（root-> right）を呼び出す

• ルートを印刷->データ

• 事前順序トラバーサルを含む入力配列としてarr[]を取ります。

• kを変数の子とします。

• 開始インデックスをcount=0とします。

• Tree_Node * node =create_tree（arr、size、children、count）を使用してツリーを構築します。

• 関数new_Node（int data）は、ツリーの新しいノードを生成します。

• 関数create_tree（int arr []、int N、int k、int height、int＆count）は、配列arr[]からkaryツリーを生成します。

• ノードの数が<=0の場合、NULLを返し、ツリーを構築できません。

• arr[]の最初の要素であるnewNode=new_Node（arr [count]）を初期化します。

• （newNode ==NULL）の結果がtrueの場合、ツリーは不可能です。

• i=0からiまでのforループを使用してarr[]をトラバースします。

• （count 1）の場合、次のインデックスのカウントをインクリメントし、newNode−> root.push_back（create_tree（arr、N、k、height − 1、count））を使用してこのノードをツリーに追加します。

• それ以外の場合は、newNode-> root.push_back（NULL）;

  を使用してNULLをプッシュしてツリーを終了します。

• 最後に、ノードへのポインタを返します。

• 関数create_tree（int * arr、int N、int k、int count）は、ツリーの高さを返します。

• 高さを計算=（int）ceil（log（（double）N *（k − 1）+ 1）/ log（（double）k））;

• 上で計算された高さのツリーのreturnステートメントでcreate_tree（arr、N、k、height、count）を呼び出します。

• 関数postorder_traversal（Tree_Node * node、int k）は、ノードをルートとするk-aryツリーのpreordertraversalを出力します。

• ノードがNULLの場合、何も返しません。

• forループを使用してi=0からi root [i]、k）;

• ノード->forループの最後にアドレスを出力します。

例

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
   int address;
   vector<Tree_Node*> root;
};
Tree_Node* new_Node(int data){
   Tree_Node* newNode = new Tree_Node;
   newNode−>address = data;
   return newNode;
}
Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
   if(N <= 0){
      return NULL;
   }
   Tree_Node* newNode = new_Node(arr[count]);
   if (newNode == NULL){
      cout<<"Code Dumped";
      return NULL;
   }
   for(int i = 0; i < k; i++){
      if (count < N − 1 && height > 1){
         count++;
         newNode−>root.push_back(create_tree(arr, N, k, height − 1, count));
      }else{
         newNode−>root.push_back(NULL);
      }
   }
   return newNode;
}
Tree_Node* create_tree(int* arr, int N, int k, int count){
   int height = (int)ceil(log((double)N * (k − 1) + 1) / log((double)k));
   return create_tree(arr, N, k, height, count);
}
void preorder_traversal(Tree_Node* node, int k){
   if (node == NULL){
      return;
   }
   for(int i = 0; i < k; i++){
      preorder_traversal(node−>root[i], k);
   }
   cout<<node−>address<< " ";
}
int main(){
   int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
   int size = 8;
   int children = 2;
   int count = 0;
   Tree_Node* node = create_tree(arr, size, children, count);
   cout<<"Construct the full k−ary tree from its preorder traversal are: ";
   preorder_traversal(node, children);
   return 0;
}

出力

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

Construct the full k-ary tree from its preorder traversal are: 3 6 1 2 1 7 5 2