Preorder Traversal ของ N-ary Tree โดยไม่ใช้ Recursion ใน C++

ในปัญหานี้ เราได้รับ N-ary Tree งานของเราคือพิมพ์ preorder traversal ของต้นไม้

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

N-ary Tree เป็นต้นไม้ที่โหนดทั้งหมดสามารถมีโหนดลูกได้สูงสุด N ตัว ตัวอย่าง 2-ary (binary) tree มีลูกสูงสุด 2 ตัว

Preorder Traversal เป็นวิธีการเดินทางโหนดของต้นไม้ ในนี้เราจะเดินทางโหนดรากก่อน แล้วลูกซ้าย และจากนั้นลูกขวา

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหาของเรา

Preorder traversal : 12 15 14 99 4 11 7 19

ในการแก้ปัญหานี้ เราต้องใช้โครงสร้างข้อมูล Stack เราจะ push root node ลงใน stack ก่อน แล้ว pop และพิมพ์มัน สำหรับทุกโหนดที่ pop เราจะ push child nodes ลงใน stack จากลูกขวาไปลูกซ้าย แล้ว pop เมื่อ push child nodes ครบแล้ว ทำซ้ำกระบวนการนี้จนกว่า stack จะว่าง

โปรแกรมแสดงการนำวิธีแก้ปัญหาของเราไปใช้

ตัวอย่างโค้ด

#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