Nhân đôi cây nhị phân (Double Tree) trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ học cách "nhân đôi" một cây nhị phân - tức là với mỗi node gốc, tạo thêm một node mới có cùng giá trị và chèn vào vị trí con trái, đẩy node con trái cũ xuống làm con của node mới.

Ý tưởng thuật toán

Duyệt cây theo thứ tự hậu tự (post-order):

1. Đệ quy xử lý cây con trái
2. Đệ quy xử lý cây con phải
3. Tạo node mới với cùng giá trị node hiện tại
4. Node mới trở thành con trái, node con trái cũ trở thành con trái của node mới

Mã nguồn hoàn chỉnh

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

class node {
public:
    int data;
    node* left;
    node* right;
};

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

void doubleTree(node* Node) {
    node* oldLeft;
    if (Node == NULL) return;
    
    doubleTree(Node->left);
    doubleTree(Node->right);
    
    oldLeft = Node->left;
    Node->left = newNode(Node->data);
    Node->left->left = oldLeft;
}

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

int main() {
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    
    cout << "Cây gốc:" << endl;
    printTree(root);
    cout << endl;
    
    doubleTree(root);
    
    cout << "Cây sau khi nhân đôi:" << endl;
    printTree(root);
    cout << endl;
    
    return 0;
}

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

Cây gốc: 2 1 3
Cây sau khi nhân đôi: 2 2 1 1 3 3

Minh họa biến đổi

Cây gốc:

    1
   / \
  2   3

Cây sau khi nhân đôi:

      1
     / \
    1   3
   /   /
  2   3
 /
2

Duyệt inorder: 2 2 1 1 3 3

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

• Thời gian: O(n) - thăm mỗi node một lần
• Không gian: O(h) - stack đệ quy, h là chiều cao cây

Kết luận

Kỹ thuật nhân đôi cây là bài tập kinh điển về thao tác con trỏ trong cây nhị phân, giúp rèn luyện tư duy đệ quy và quản lý bộ nhớ động.