如何在 C++ 中实现完整的二进制文件？

Question

我想尝试使用递归插入完整的二叉树。我制作了一段代码，但我无法解决为什么未插入值的问题。我在这些函数和递归调用的帮助下使高度函数和计数节点函数我想在完整的二叉树中插入新节点。在 main 中使用 get root 函数获取 root 然后发送到 insert 函数

#include<iostream>
#include<math.h>
using namespace std;
struct node{
int data;
node *left,*right;
};
class cbt{
node *root;
    

public:

cbt()
{
root=NULL;

}

node* get_node()
{
return root;
}

       node* newNode(int key)
  {
    node* temp1 = new node;
    temp1->data = key;
    temp1->left = temp1->right = NULL;

    return temp1;
  }


 
 void CBT_inseration(node* temp,int data)
 {
    node *ptr;
    ptr=newNode(data);
    if(root==NULL)
    {
        root=ptr;
        return;
    }
    else
    {
    
    
    
    height = f_height(temp->left);
    int excepted_node = pow(2,height)-1;
    int left_tree_node_count  = countNumNodes(temp->left);
    int right_tree_node_count = countNumNodes(temp->right);

    if(left_tree_node_count==right_tree_node_count)
    {
        CBT_inseration(temp->left,data);
    }
    else if(excepted_node != left_tree_node_count)
    {
        if(temp->left == NULL)
        {
            temp->left = ptr;
            return;
        }else
        {
            CBT_inseration(temp->left,data);
            
        }
    }
    else if(temp->right == NULL)
    {
        temp->right=ptr;
        return;
    }
    else if(excepted_node != left_tree_node_count)
    {
        if(temp->left == NULL)
        {
             temp->left=ptr;
            return;
        }
        else
        {
            CBT_inseration(temp->right,data);
        }
        
    }


    
}
}

void print(node *root) {
    if (root == NULL)
        return;
    print(root->left);
    cout << root->data << " ";
    print(root->right);
}





};
int main()
{
cbt obj;
node *r=NULL;
obj.CBT_inseration(obj.get_node(),4);
obj.CBT_inseration(obj.get_node(),3);
obj.CBT_inseration(obj.get_node(),5);

obj.CBT_inseration(obj.get_node(),8);
obj.print(obj.get_node());
return 0;
  }

Answer 1

您需要通过调试器来查看您的代码有什么问题。我会告诉你我会怎么做：

首先，您需要一个函数来检查树是否已满。我们将重用您的函数来执行此操作：

bool isTreeFull(node* head) {
  return head != NULL && countNumNodes(head) == (1 << find_height(head)) - 1;
}

然后为了插入我必须检查每边的节点数是否相同。这告诉我，我可以在左侧更深地移动一层。如果节点数不一样，那么我只在左子树已满的情况下继续插入右子树：

void CBT_inseration(int data) {
  root = insert(root, data);
}

node* insert(node* head, int data) {
  if (head == NULL) {
    head = newNode(data);
  } else {
    int leftCount = countNumNodes(head->left);
    int rightCount = countNumNodes(head->right);
    if (leftCount == rightCount) {
      head->left = insert(head->left, data);
    } else {
      if (isTreeFull(head->left)) {
        head->right = insert(head->right, data);
      } else {
        head->left = insert(head->left, data);
      }
    }
  }
  return head;
}

然后你会这样称呼它：

cbt obj;
obj.CBT_inseration(4);
obj.CBT_inseration(3);
obj.CBT_inseration(5);
obj.CBT_inseration(6);
obj.CBT_inseration(8);
obj.print(obj.get_node()); // 6 3 8 4 5

如何在 C++ 中实现完整的二进制文件？

How to implement complete binary in c++?

c++

binary-tree

insertion

data-structures