My task is to create a complete binary tree. The only requirements are that it be a dynamic tree with nodes and pointers - I may use temporary arrays to help with the intial tree construction. Where I need help is with the insert(Node) method. Here's what I have so far:

``````void BinaryTree::insert(int data, TreeNode* subTreeRoot, const
TreeNode*& parent)
{
TreeNode temp;
temp = subTreeRoot;

if ( subTreeRoot == NULL ) {
subTreeRoot = new TreeNode(-1,NULL,NULL,temp);
}
else if ( subTreeRoot->left == NULL ) {
}
else if ( subTreeRoot->right == NULL ) {
}
else {
}
}``````

Each node has three links and one data field - leftLink,rightLink,parent, and data. The reason for the parent link is to help with another part of the project. Basically, the problem I have is inserting the nodes in the proper "complete binary tree" method. That is, how do I insert the nodes in such a manner that all leafs are at height n or n-1 of a n tall tree? I believe the code I have right now will simply insert nodes on the far most left side, which will not create a complete binary tree. The code correctly creates a tree with a root and two children, but I believe it falls apart after that. Also, how do I keep track of the parent so that I can store that into the parent link field? I'm not sure if my current method accomplishes that.

I am trying to use a recursive method to accomplish my task, but I may have to switch to using temporary arrays.

Any help is greatly appreciated. I will be working on this all day so please reply if you have any input at all.

Thanks.

I always thought this was a good help. Well the concept anyway. The rest is just programming semantics.

What is this printout is supposed to mean?

``````Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>2

Enter a Node (9999 to finish)>21

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>2

Enter a Node …``````

## All 9 Replies

I always thought this was a good help. Well the concept anyway. The rest is just programming semantics.

I went ahead with the temporary array approach. Much more simplistic. Here is a code i hav tried to implement a sample complete binary tree......but using a different logic...........

U can try dis out...

``````#include<stdio.h>
#include<stdlib.h>

struct btree{
int id, val;
struct btree *left, *right;
};

typedef struct btree node;

void myparent(node *tree, int myid, node **parent){
if(tree->id==(myid/2))
*parent = tree;
if(tree->left)
myparent(tree->left, myid, parent);
if(tree->right)
myparent(tree->right, myid, parent);
}

void insert(node **tree, node *item){
node *parent;
if(item->id==1)
*tree=item;
else{
myparent(*tree, item->id,&parent);
if((item->id)%2)
parent->right=item;
else
parent->left=item;
}
}

void printout(node *tree){
if(tree->left)
printout(tree->left);
printf("%d\n", tree->val);
if(tree->right)
printout(tree->right);
}

main(){
node *root, *curr;
int idcount=1, inp=0;
root=NULL;
//input 9999 is the exit point
while(inp!=9999){
printf("\nEnter a Node>");
scanf("%d",&inp);
curr=(node*)malloc(sizeof(node));
curr->val=inp;
curr->id=idcount++;
curr->left = curr->right = NULL;
insert(&root, curr);
}

printf("\n Entered Binary Tree is \n");
printout(root);
return 0;
}``````

The logic is explained below........... The logic is by putting an extra property 'id' for each node..............

Consider d eg tree

``````A(1)
B(2)                                         C(3)
D(4)                 E(5)                     F(6)             G(7)
H(8)    I(9)         J(10)   K(11)            L(12)   M(13)     N(14) O(15)``````

here the no on the () are the ids of each node.....from d above eg u wil came to knw dat for every node with id x its parent node will be with id x/2...except d root

so d thing u have to do while inserting is dat identify d parent for each node...for dat u can use d basic tree taversal methods...

commented: Should learn to write. -3

What is this printout is supposed to mean?

``````Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>2

Enter a Node (9999 to finish)>21

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>2

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>2

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>1

Enter a Node (9999 to finish)>9999

Entered Binary Tree is
2
21
1
1
1
1
9999
1
2
2
1

Process returned 0 (0x0)   execution time : 18.062 s
Press any key to continue.`````` The function printout() shows the inorder traversed tree. You could verify it with the example inputs you have given.
The complete binary tree will be like this.

``````1(a)

1(b)                                                   2(c)

21(d)                       1(e)                          2(f)                          1(g)

2(h)            1(i)           1(j)    9999(k)``````

The inorder traversal of the above tree gives the following output.
2(h),21(d),1(i),1(b),1(j),1(e),9999(k),1(a),2(f),2(c),1(g)

``````//Complete Binary Tree...
//Leaf nodes as left as possible and ...
//All levels except last must be full...

//Queue is used for insertion in Tree...
//Queue implemented as Circular Queue...

#include<iostream.h>
class node;

class queue
{
node** q;
int max;
int front,rear;
public:
queue()
{
front=-1;
rear=-1;
max=10;
q=new (node*);
}
queue(int n)
{

front=-1;
rear=-1;
max=n;
q=new (node*)[n];
}

void enque(node* n)
{
if((front==0 && rear==max-1)||(front==rear+1))
{
cout<<"\nOverflow !!!";
}
else
{
cout<<"\nEnque"<<n;

if( front==-1)
{
front=0;
rear=0;
q[front]=n;
}
else if(rear==max-1)
{
rear=0;
}
else
rear++;
q[rear]=n;
}

}

node* deque()
{
if(front==-1)
{
cout<<"\nUnderflow !!!";
return NULL;
}
else
{
node* item=q[front];
cout<<"\nDeque"<<item;

if(rear==front)
rear=front=-1;
else if(front==max-1)
front=0;
else
front++;

return item;
}
}

node* peek()
{
if(front==-1)
{
cout<<"\nUnderflow !!!";
return NULL;
}
else
return q[front];
}
}q(20);

class node
{
int info;
node* left,*right;

public:

void insert(node **root,int n)
{
if((*root)==NULL)
{
(*root)=new node;
(*root)->info=n;
(*root)->left=NULL;
(*root)->right=NULL;
q.enque((*root));
}
else
{
node* nd=q.peek();
if(nd->left==NULL)
{
nd->left=new node;
q.enque(nd->left);
nd=nd->left;
nd->info=n;
nd->left=nd->right=NULL;
}
else
{
nd=q.deque();
nd->right=new node;
q.enque(nd->right);
nd=nd->right;
nd->info=n;
nd->left=nd->right=NULL;
}
}
}

void inorder(node * ptr)
{
if(ptr->left!=NULL)
inorder(ptr->left);
cout<<"\n--"<<ptr->info;
if(ptr->right!=NULL)
inorder(ptr->right);
}
};

void main()
{
int a[]={1,2,3,4,5,6,7};
node n,*root=NULL;
for(int i=0;i<7;i++)
n.insert(&root,a[i]);
n.inorder(root);
}
``````
commented: This thread is YEARS old! Let sleeping dogs sleep... -3

Initially for very first node, the node is just inserted in the queue (root of the tree).
For others, we perform peek on the queue- it returns the front element in queue without deleting it.
.
Now if its left node is Null, then we insert the new node to the left.
This new node also inserted into the queue.
.
Else, we dequeue node (deleted from queue and then returned) and the new node is inserted to right.
Again this new node also inserted into the queue. ``````#include<iostream>
#include<cstdlib>
using namespace std;
struct bt
{
bt *lchild;
int data;
bt *rchild;
};
int size=10;
class queue
{
public:
int r,f;
bt *a;
void inque(bt *b);
bt *deque( );
}q1,q2;
void queue::inque(bt *b)
{
r=(r+1)%size;
a[r]=b;
if(f==-1)f=f+1;
}
bt *queue::deque( )
{
bt* ret=a[f];
if(f==r)f=r=-1;
else
f=(f+1)%size;
return ret;
}
bt *newnode(bt *t,int a)
{
if(a==-1){t=new(bt);t=NULL;}
else
{
t=new(bt);
t->lchild=NULL;
t->rchild=NULL;
t->data=a;
}
return t;
}
void create(bt *&t,int a)
{
bt *t1,*t2,*p,*t4,*t3;
t2=NULL;
int i=0;
t=new(bt);t->data=a;t->lchild=NULL;t->rchild=NULL;
q1.inque(t);
while(1)
{
while(q1.f!=-1)
{
p=q1.deque( );
cout<<"enter lchild of "<<p->data;
cin>>a;q2.inque(newnode(t2,a));
cout<<"enter rchild of "<<p->data;
cin>>a;q2.inque(newnode(t2,a));
}
if(i==0){q1.inque(t);i++;}
while(q2.f!=-1)
{
t1=q1.deque();
t3=q2.deque();
t4=q2.deque();
if(t3!=NULL){q1.inque(t3);t1->lchild=new(bt); t1->lchild=t3;}
if(t4!=NULL){q1.inque(t4);t1->rchild=new(bt);t1->rchild=t4;}
}
if(q1.f==-1&&q2.f==-1)break;
}
}
void print(bt *t)
{
if(t!=NULL)
{cout<<t->data;}
if(t->lchild!=NULL)print(t->lchild);
if(t->rchild!=NULL)print(t->rchild);
}
int main( )
{
bt  *t;
t=NULL;
q1.f=-1;
q1.r=-1;
q2.f=-1;
q2.r=-1;
int a;
cout<<"enter no \n";
cin>>a;
create(t,a);
print(t);
return 0;
}
``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.