Chuyển đổi cây nhị phân thành cây đối xứng (Mirror Tree) trong C++

Cây đối xứng (mirror tree) của một cây nhị phân là cây được tạo bằng cách hoán đổi cây con trái và phải của mọi nút.

Thuật toán: Duyệt post-order, tại mỗi nút hoán đổi con trỏ left và right.

Ví dụ minh họa (C++)

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

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* newNode(int data) {
    Node* node = new Node();
    node->data = data;
    node->left = node->right = nullptr;
    return node;
}

void mirror(Node* node) {
    if (!node) return;
    mirror(node->left);
    mirror(node->right);
    swap(node->left, node->right); // Hoán đổi hai con trỏ
}

void print_tree(Node* node) {
    if (!node) return;
    print_tree(node->left);
    cout << node->data << " ";
    print_tree(node->right);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    cout << "Inorder cay goc: ";
    print_tree(root);
    mirror(root);
    cout << "\nInorder cay doi xung: ";
    print_tree(root);
    return 0;
}

Kết quả

Inorder cay goc: 4 2 5 1 3
Inorder cay doi xung: 3 1 5 2 4