ตัวแทรกต้นไม้แบบทวิภาคสมบูรณ์ใน C++

ต้นไม้แบบทวิภาคสมบูรณ์ (Complete Binary Tree) คือต้นไม้ที่ทุกระดับยกเว้นระดับสุดท้ายเต็มไปหมด และโหนดทั้งหมดชิดซ้ายที่สุด เราต้องเขียนโครงสร้างข้อมูล CBTInserter ที่รองรับ:

• CBTInserter(TreeNode root) เริ่มต้นด้วยต้นไม้ที่กำหนด
• CBTInserter.insert(int v) แทรกโหนดค่า v ให้ต้นไม้ยังคงสมบูรณ์ คืนค่าของพ่อของโหนดที่แทรก
• CBTInserter.get_root() คืนโหนดราก

ตัวอย่าง: เริ่มต้น [1,2,3,4,5,6] แทรก 7 และ 8 ได้รากคืน [1,2,3,4,5,6,7,8] ค่าที่คืนคือ 3 และ 4 (เพราะ 7 อยู่ใต้ 3, 8 อยู่ใต้ 4)

ขั้นตอนการแก้ปัญหา (Queue สำหรับติดตามพ่อที่มีช่องว่าง)

• คิว q และ root
• คอนสตรัคเตอร์: ใส่ root เข้า q แล้ววนลูป:
  • ถ้ามีลูกซ้าย ใส่เข้า q มิฉะนั้น break
  • ถ้ามีลูกขวา ใส่เข้า q และลบหน้าคิวออก (พ่อคนนั้นเต็มแล้ว) มิฉะนั้น break
• insert(v):
  • parent := q.front(), สร้างโหนดใหม่ temp ใส่เข้า q
  • ถ้า parent ไม่มีลูกซ้าย: ตั้งลูกซ้าย = temp
  • มิฉะนั้น: ลบหน้าคิวออก ตั้งลูกขวา = temp
  • คืนค่า parent.val
• getRoot() คืน root

ตัวอย่างโค้ด (C++)

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        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 == NULL) return;
    cout << "[";
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        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 == NULL || 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;
    cout << (ob.insert(8)) << endl;
    tree_level_trav(ob.get_root());
}

อินพุต

Initialize the tree as [1,2,3,4,5,6], then insert 7 and 8 into the tree, then find root

เอาต์พุต

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