How to implement complete binary in c++?

Question

I want to try make insertion of complete binary tree using recursion . I make a piece of code and I cannot catch problem why value not inserted. I make height function and count nodes function with help of these function and recursive call I want to insert new node in Complete binary tree. In main get root by using get root function then send to insert function

#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;
  }

Step 1: Format (i.e. indent) your code consistently. Without that, it's hard to read and understand. This will help you find the error and it will attract others to read your code here as well. Make sure what you post here also qualifies as minimal reproducible example. As a new user, please also take the tour and read How to Ask. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Dec 5, 2020 at 20:07
Read the documentation of your C++ compiler (e.g. GCC...) and of your debugger (e.g. GDB..). Then read Introduction to Algorithms and a good C++ programming book. You may want to use std::set and to study its implementation inside GCC (which is free software): you are allowed to download the source code of GCC — Basile Starynkevitch
– Basile Starynkevitch, Commented Dec 6, 2020 at 5:33

David G · Accepted Answer · 2020-12-06 18:33:56Z

You would need to go through a debugger to see what is wrong with your code. I will tell you how I would do this:

First, you need a function to check if the tree is full. We will reuse your functions to do this:

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

Then for inserting I have to check if the number of nodes on each side are the same. This tells me that I am allowed to move one level deeper on the left side. If the number of nodes aren't the same, then I only move on to insert on the right subtree if the left subtree is full:

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;
}

Then you would call it like:

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

Collectives™ on Stack Overflow

How to implement complete binary in c++?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related