Bộ chèn cây nhị phân hoàn chỉnh trong C++

Cây nhị phân hoàn chỉnh (complete binary tree): mọi cấp trừ có thể cấp cuối đều đầy, nút ch gravitates trái. Thiết kế CBTInserter:

• CBTInserter(TreeNode root): khởi tạo với cây hoàn chỉnh.
• insert(int v): chèn nút giá trị v giữ tính hoàn chỉnh, trả về giá trị cha.
• get_root(): trả về gốc cây.

Ví dụ: khởi tạo [1,2,3,4,5,6], insert 7, 8 → Trả về cha: 3, 4. Cây: [1,2,3,4,5,6,7,8].

Giải thuật (Hàng đợi nút chưa đủ 2 con)

1. Hàng đợi q lưu các nút chưa có đủ 2 con (theo thứ tự cấp).
2. Khởi tạo: push root vào q, duyệt BFS: nếu nút có con trái, push con trái; nếu có con phải, push con phải và pop nút cha (đã đủ 2 con).
3. insert(v): parent = q.front(), tạo temp giá trị v, push temp vào q.
4. Nếu parent->left null → gán left = temp; ngược lại → pop q, gán right = temp.
5. Trả về parent->val.

Ví dụ C++

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

class TreeNode {
public:
    int val; TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front(); q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0); return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0); return;
        } else q.push(temp->right);
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

void tree_level_trav(TreeNode* root) {
    if(!root) return;
    cout << "[";
    queue<TreeNode*> q; q.push(root); q.push(NULL);
    while(q.size() > 1) {
        TreeNode* curr = q.front(); q.pop();
        if(curr == NULL) { q.push(NULL); }
        else {
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            if(curr->val == 0) cout << "null, ";
            else cout << curr->val << ", ";
        }
    }
    cout << "]" << endl;
}

class CBTInserter {
public:
    queue<TreeNode*> q;
    TreeNode* root;
    CBTInserter(TreeNode* root) {
        this->root = root; q.push(root);
        while(1) {
            if(root->left) q.push(root->left);
            else break;
            if(root->right) { q.push(root->right); q.pop(); root = q.front(); }
            else break;
        }
    }
    int insert(int v) {
        TreeNode* parent = q.front();
        TreeNode* temp = new TreeNode(v);
        q.push(temp);
        if(!parent->left) parent->left = temp;
        else { q.pop(); parent->right = temp; }
        return parent->val;
    }
    TreeNode* get_root() { return root; }
};

int main() {
    vector<int> v = {1,2,3,4,5,6};
    TreeNode *root = make_tree(v);
    CBTInserter ob(root);
    cout << ob.insert(7) << endl; // 3
    cout << ob.insert(8) << endl; // 4
    tree_level_trav(ob.get_root());
    return 0;
}

Đầu vào

Khởi tạo cây [1,2,3,4,5,6], insert 7, 8, lấy root

Đầu ra

3 4 [1, 2, 3, 4, 5, 6, 7, 8, ]