Như chúng ta đã biết một cây nhị phân hoàn chỉnh là một cây nhị phân trong đó mọi cấp, ngoại trừ cấp cuối cùng, đều được lấp đầy hoàn toàn và tất cả các nút ở bên trái càng xa càng tốt. Chúng ta phải viết một cấu trúc dữ liệu CBTInserter được khởi tạo bằng một cây nhị phân hoàn chỉnh và nó hỗ trợ các hoạt động sau−
-
CBTInserter (TreeNode gốc) khởi tạo cấu trúc dữ liệu trên một cây nhất định có gốc nút đầu;
-
CBTInserter.insert (int v) sẽ được sử dụng để chèn một TreeNode vào cây với giá trị node.val =v để cây vẫn hoàn chỉnh và trả về giá trị gốc của TreeNode được chèn vào;
-
CBTInserter.get_root () điều này sẽ trả về nút đầu của cây.
Vì vậy, ví dụ, nếu chúng ta khởi tạo cây là [1,2,3,4,5,6], sau đó chèn 7 và 8, sau đó cố gắng lấy cây, kết quả sẽ là:3, 4, [1,2 , 3,4,5,6,7,8], 3 là vì 7 sẽ được chèn dưới 3, và 4 là vì 8 sẽ được chèn dưới 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định hàng đợi q và gốc
-
Trình khởi tạo sẽ lấy cây nhị phân đầy đủ, sau đó hoạt động như sau
-
đặt root dưới dạng root đã cho, chèn root vào q
-
trong khi đúng -
-
nếu có bên trái của gốc thì chèn bên trái của gốc vào q, nếu không thì sẽ phá vỡ vòng lặp
-
nếu có quyền gốc thì chèn quyền gốc vào q và xóa nút phía trước khỏi q, nếu không sẽ phá vỡ vòng lặp
-
-
Từ phương thức chèn, nó sẽ nhận giá trị v
-
đặt phần tử cha:=phía trước của q, temp:=nút mới với giá trị v và chèn nó vào q
-
nếu bên trái của cha không có mặt, thì đặt bên trái của cha:=temp, nếu không hãy xóa phần tử phía trước khỏi q và chèn temp làm phần tử con bên phải của cha
-
trả về giá trị của cha mẹ
-
từ phương thức getRoot (), trả về gốc
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#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;
}
};
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());
} Đầu vào
Initialize the tree as [1,2,3,4,5,6], then insert 7 and 8 into the tree, then find root
Đầu ra
3 4 [1, 2, 3, 4, 5, 6, 7, 8, ]