用C ++完成的二叉树插入器

众所周知，完整的二叉树是一棵二叉树，其中除最后一个级别外，每个级别都被完全填充，并且所有节点都尽可能地靠左。我们必须编写一个数据结构CBTInserter，并使用完整的二进制树对其进行初始化，并且它支持以下操作：

• CBTInserter（TreeNode root）初始化具有根节点根的给定树上的数据结构；

• CBTInserter.insert（int v）将用于将TreeNode插入到具有值node.val = v的树中，以使树保持完整，并返回所插入TreeNode的父级的值；

• CBTInserter.get_root()这将返回树的头节点。

因此，例如，如果我们将树初始化为[1,2,3,4,5,6]，然后插入7和8，然后尝试获取树，则输出将是：3，4，[1,2 ，3,4,5,6,7,8]，则3是因为在3下插入了7，而4是因为在4下插入了8。

为了解决这个问题，我们将遵循以下步骤-

• 定义队列q和根

• 初始化程序将采用完整的二叉树，然后按以下方式工作

• 将root设置为给定root，将root插入q

• 虽然为真-

• 如果存在root的左边，则将root的左边插入q，否则中断循环

• 如果存在root的权利，则将root的权利插入q并从q删除前节点，否则中断循环

• 从insert方法中，它将取值v

• 设置parent：= q的前元素，temp：=值为v的新节点，并将其插入q

• 如果不存在parent的左边，则将parent设置为左边：= temp，否则从q中删除前元素，并将temp插入为parent的右孩子

• 返回parent的值

• 从getRoot()方法中返回根

例子（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;
   }
};
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, ]