สั่งซื้อล่วงหน้า Traversal ของ N-ary Tree โดยไม่มี Recursion ใน C++

ในปัญหานี้ เราได้รับ N-ary Tree งานของเราคือการพิมพ์การสั่งจองล่วงหน้าของต้นไม้

ก่อนอื่น มาเรียนรู้คำศัพท์พื้นฐานกัน

ต้นไม้นารี เป็นต้นไม้ที่โหนดทั้งหมดสามารถมีโหนดย่อยได้สูงสุด 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