Tạo cây đối xứng từ cây nhị phân cho trước trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ học cách tạo cây đối xứng (mirror tree) từ một cây nhị phân cho trước bằng ngôn ngữ C++.

Các bước thực hiện

1. Định nghĩa cấu trúc node của cây nhị phân
2. Xây dựng cây nhị phân với dữ liệu mẫu
3. Viết hàm đệ quy để tạo cây đối xứng
4. In kết quả cây trước và sau khi đối xứng

Giải thuật

Ý tưởng chính là duyệt cây theo thứ tự hậu tự (post-order) và hoán đổi con trỏ left và right của mỗi node:

• Gọi đệ quy cho node con trái
• Gọi đệ quy cho node con phải
• Hoán đổi con trỏ left và right của node hiện tại

Mã nguồn hoàn chỉnh

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

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

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

void convertTreeToItsMirror(struct Node* node) {
    if (node == NULL) {
        return;
    } else {
        struct Node* temp;
        convertTreeToItsMirror(node->left);
        convertTreeToItsMirror(node->right);
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}

void printTree(struct Node* node) {
    if (node == NULL) {
        return;
    }
    printTree(node->left);
    cout << node->data << " ";
    printTree(node->right);
}

int main() {
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    
    cout << "Cây gốc: ";
    printTree(root);
    cout << endl;
    
    convertTreeToItsMirror(root);
    
    cout << "Cây đối xứng: ";
    printTree(root);
    cout << endl;
    
    return 0;
}

Kết quả chạy chương trình

Cây gốc: 4 2 5 1 3
Cây đối xứng: 3 1 5 2 4

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt qua tất cả n node của cây
• Không gian: O(h) - độ sâu đệ quy tối đa bằng chiều cao cây h

Kết luận

Chương trình minh họa cách tạo cây đối xứng bằng thuật toán đệ quy đơn giản. Kỹ thuật này hữu ích trong nhiều bài toán liên quan đến cây nhị phân.