C++での再帰なしのN-aryツリーのプレオーダートラバーサル

この問題では、N-aryツリーが与えられます。私たちのタスクは、ツリーのプレオーダートラバーサルを印刷することです。

まず、いくつかの基本的な用語を学びましょう。

N-aryツリー は、すべてのノードが最大N個の子ノードを持つことができるツリーです。例2-ary（バイナリ）ツリーには最大2つの子ノードがあります。

プレオーダートラバーサル ツリーのノードをトラバースする方法です。ここでは、最初にルートノードをトラバースし、次に左の子、次に右の子をトラバースします。

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

Preorder traversal :
12151499411719

この問題を解決するには、スタックデータ構造を使用する必要があります。まず、ルートノードをスタックにプッシュします。次に、それをポップして印刷します。ポップされたノードごとに、スタックの子ノードを右の子から左の子にプッシュします。次に、すべての子ノードがプッシュされたときにポップします。スタックが空になるまでこのプロセスを繰り返します。

ソリューションの実装を示すプログラム

例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int key;
   vector<Node*> child;
};
Node* insertNode(int key){
   Node* temp = new Node;
   temp->key = key;
   return temp;
}
void preOrderTraversal(struct Node* root){
   stack<Node*> tree;
   tree.push(root);
   while (!tree.empty()) {
      Node* curr = tree.top();
      tree.pop();
      cout<<curr->key<<"\t";
      vector<Node*>::iterator it = curr->child.end();
      while (it != curr->child.begin()) {
         it--;
         tree.push(*it);
      }
   }
}
int main(){
   Node* root = insertNode(12);
   (root->child).push_back(insertNode(15));
   (root->child).push_back(insertNode(99));
   (root->child).push_back(insertNode(4));
   (root->child).push_back(insertNode(7));
   (root->child[0]->child).push_back(insertNode(1));
   (root->child[0]->child).push_back(insertNode(4));
   (root->child[0]->child).push_back(insertNode(25));
   (root->child[2]->child).push_back(insertNode(11));
   (root->child[3]->child).push_back(insertNode(19));
   cout<<"PreOrder Traversal of the tree is :\n";
   preOrderTraversal(root);
   return 0;
}

出力

PreOrder Traversal of the tree is :
12   15   14   25   99   4   11   7   19