Coding a Complete Binary Tree

[rabbit337]

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 ) {
               insert(data,subTreeRoot->leftLink,temp);
        }
        else if ( subTreeRoot->right == NULL ) {
               insertNode (data,subTreeRoot->rightLink,temp);
        }
        else {
               insert(data,subTreeRoot->leftLink,subTreeRoot->leftLink);
               insert(data,subTreeRoot->rightLink,subTreeRoot->rightLink);
        }                
}

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.

[iamthwee]

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

http://cslibrary.stanford.edu/110/BinaryTrees.html

[rabbit337]

I went ahead with the temporary array approach. Much more simplistic.

[riazcp]

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...........

[riazcp]

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...

[TrustyTony]

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.

[riazcp]

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)

[pankaj.leon]

//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*)[10];
    }
    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);
}

[pankaj.leon]

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.

[sonu_1]

#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[10];
 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;
}