C++에서 재귀 없는 N-ary 트리의 선주문 순회

이 문제에서는 N-ary Tree가 주어집니다. 우리의 임무는 트리의 선주문 순회를 인쇄하는 것입니다.

먼저 몇 가지 기본 용어를 알아보겠습니다.

N-ary 트리 모든 노드가 최대 N개의 자식 노드를 가질 수 있는 트리입니다. 예제 2-ary(binary) 트리에는 최대 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