Đề bài
Cho một cây mà mỗi nút chứa số lượng con biến đổi, chuyển đổi cây thành đối xứng của nó.
Ví dụ
Nếu cây n-ary là:
Thì đối xứng của nó là:
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; struct node { int data; vector<node *>child; }; 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; } queue<node *>q; 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; i<p->child.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; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
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