โปรแกรม C++ สร้างภาพกระจกของ n-ary Tree

ข้อความโจทย์

กำหนดต้นไม้ที่ทุกโหนดมีจำนวนลูกที่แตกต่างกัน แปลงต้นไม้ให้เป็นภาพกระจก

ตัวอย่าง

ถ้า n-ary tree คือ:

ภาพกระจกจะเป็น:

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

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data;
    vectorchild;
};

node *newNode(int x) {
    node *temp = new node;
    temp->data = x;
    return temp;
}

void mirrorTree(node * root) {
    if (root == NULL) {
        return;
    }
    int n = root->child.size();
    if (n < 2) {
        return;
    }
    for (int i = 0; i < n; i++) {
        mirrorTree(root->child[i]);
    }
    reverse(root->child.begin(), root->child.end());
}

void printTree(node * root) {
    if (root == NULL) {
        return;
    }
    queueq;
    q.push(root);
    int level = 0;
    while (!q.empty()) {
        int n = q.size();
        ++level;
        cout << "Level " << level << ": ";
        while (n > 0) {
            node * p = q.front();
            q.pop();
            cout << p->data << " ";
            for (int i=0; ichild.size(); i++) {
                q.push(p->child[i]);
            }
            n--;
        }
        cout << endl;
    }
}

int main() {
    node *root = newNode(20);
    (root->child).push_back(newNode(10));
    (root->child).push_back(newNode(15));
    (root->child[0]->child).push_back(newNode(1));
    (root->child[0]->child).push_back(newNode(2));
    (root->child[0]->child).push_back(newNode(3));
    (root->child[1]->child).push_back(newNode(4));
    cout << "Tree traversal before mirroring\n";
    printTree(root);
    mirrorTree(root);
    cout << "\nTree traversal after mirroring\n";
    printTree(root);
    return 0;
}

ผลลัพธ์

Tree traversal before mirroring
Level 1: 20
Level 2: 10 15
Level 3: 1 2 3 4
Tree traversal after mirroring
Level 1: 20
Level 2: 15 10
Level 3: 4 3 2 1