Chuyển cây nhị phân thành cây tìm kiếm nhị phân dùng STL set trong C++

Cho một cây nhị phân (Binary Tree), chuyển thành cây tìm kiếm nhị phân (BST) nhưng giữ nguyên cấu trúc gốc của cây nhị phân.

Giải pháp dùng set của C++ STL thay vì mảng.

Ví dụ

Ví dụ 1

Đầu vào

    11
   /  \
  3    8
 / \  
9   5

Đầu ra

    9
   / \
  5   11
 /     \
3       8

Ví dụ 2

Đầu vào

    11
   /  \
  31   16
 / \   
21  6  

Đầu ra

    16
   /  \
  11   21
 /  \   
6    31

Giải pháp

• Duyệt inorder cây nhị phân, lưu các nút vào set. Phép chèn O(log n), tổng O(n log n). set trong C++ dùng cây cân bằng (Red-Black, AVL...).
• Không cần sắp xếp set vì set tự sắp xếp nhờ cây cân bằng.
• Duyệt inorder cây, lần lượt lấy phần tử đầu set (nhỏ nhất) gán vào nút, xóa khỏi set. Lặp cho đến hết.
• Cách này đơn giản, dễ triển khai hơn dùng mảng.

Chương trình C++

/* CPP chuyển Binary tree sang BST dùng set */ 
#include <bits/stdc++.h>
using namespace std;

struct Node1 {
    int data;
    struct Node1 *left, *right;
};

// Lưu nút vào set khi duyệt inorder
void storeinorderInSet(Node1* root1, set<int>& s) {
    if (!root1) return;
    storeinorderInSet(root1->left, s);
    s.insert(root1->data); // O(log n)
    storeinorderInSet(root1->right, s);
}

// Copy từ set sang cây khi duyệt inorder
void setToBST(set<int>& s, Node1* root1) {
    if (!root1) return;
    setToBST(s, root1->left);
    auto it = s.begin();
    root1->data = *it;
    s.erase(it);
    setToBST(s, root1->right);
}

// Chuyển Binary tree sang BST
void binaryTreeToBST(Node1* root1) {
    set<int> s;
    storeinorderInSet(root1, s);
    setToBST(s, root1);
}

// Tạo nút mới
Node1* newNode(int data) {
    Node1* temp = new Node1();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// Duyệt inorder
void inorder(Node1* root1) {
    if (!root1) return;
    inorder(root1->left);
    cout << root1->data << " ";
    inorder(root1->right);
}

int main() {
    Node1* root1 = newNode(6);
    root1->left = newNode(8);
    root1->right = newNode(10);
    root1->right->left = newNode(11);
    root1->left->left = newNode(2);
    root1->left->right = newNode(7);
    root1->right->right = newNode(12);
    /*
         6
        / \
       8  10
      /\  / \
     2 7 11 12
    */
    binaryTreeToBST(root1);
    cout << "Inorder traversal of BST is: " << endl;
    inorder(root1);
    return 0;
}

Kết quả

Inorder traversal of BST is: 1 5 6 7 9 10 11

Độ phức tạp thời gian: O(n log n)

Không gian phụ助: O(n) cho set.