Duyệt tiền tố của cây N-ary không dùng đệ quy trong C++

Trong bài toán này, chúng ta được cho một cây N-ary. Nhiệm vụ của chúng ta là in duyệt tiền tố của cây.

Trước tiên, hãy học một số thuật ngữ cơ bản:

Cây N-ary là một cây mà tất cả các nút có thể có tối đa N nút con. Ví dụ: cây 2-ary (nhị phân) có tối đa 2 nút con.

Duyệt tiền tố là một cách để duyệt các nút của cây. Trong này, chúng ta sẽ trước tiên duyệt nút gốc, sau đó nút con trái và rồi nút con phải.

Hãy xem một ví dụ để hiểu bài toán của chúng ta:

Duyệt tiền tố : 12 15 14 99 4 11 7 19

Để giải quyết bài toán này, chúng ta phải sử dụng cấu trúc dữ liệu stack. Chúng ta sẽ trước tiên đẩy nút gốc vào stack. Sau đó pop nó và in ra. Đối với mỗi nút được pop, chúng ta sẽ đẩy các nút con của stack từ con phải đến con trái. Sau đó pop khi tất cả các nút con đã được đẩy. Lặp lại quá trình này cho đến khi stack rỗng.

Chương trình minh họa triển khai giải pháp của chúng ta:

Ví dụ

#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<<"Duyệt tiền tố của cây là :\n";
    preOrderTraversal(root);
    return 0;
}

Kết quả

Duyệt tiền tố của cây là :
12   15   14   25   99   4   11   7   19