Ad:

C Discussion Thread
Unsolved
Views: 6750

Mar 2nd, 2007

Coding a Complete Binary Tree

Expand Post »

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:

C Syntax (Toggle Plain Text)
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);
        }                
}
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.

Last edited by Narue; May 19th, 2011 at 9:06 am. Reason: Added code tags

Similar Threads

C++ complete binary tree using an array. Unexpected end file in C++
complete binary tree using an array help in C++
Question about binary tree & heaps in Computer Science
coding a complete binary tree with Dev-C++ in C++

rabbit337

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Mar 2007

Permalink

Mar 2nd, 2007

Re: Coding a Complete Binary Tree

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

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Mar 2nd, 2007

Re: Coding a Complete Binary Tree

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

rabbit337

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Mar 2007

Permalink

May 19th, 2011

Re: Coding a Complete Binary Tree

Here is a code i hav tried to implement a sample complete binary tree......but using a different logic...........

U can try dis out...

C Syntax (Toggle Plain Text)
#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;
}
#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...........

Last edited by riazcp; May 19th, 2011 at 6:36 am. Reason: Advancement

riazcp

Reputation Points: 7

Solved Threads: 0

Newbie Poster

Offline

3 posts
since May 2011

Permalink

May 19th, 2011

-1

Re: Coding a Complete Binary Tree

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

Consider d eg tree

C Syntax (Toggle Plain Text)
                                         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)
                                         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...

Last edited by riazcp; May 19th, 2011 at 6:47 am.

riazcp

Reputation Points: 7

Solved Threads: 0

Newbie Poster

Offline

3 posts
since May 2011

Permalink

May 19th, 2011

Re: Coding a Complete Binary Tree

What is this printout is supposed to mean?

C Syntax (Toggle Plain Text)
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.
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.

pyTony

Featured Poster

Reputation Points: 687

Solved Threads: 748

Industrious Poster

Offline

4,208 posts
since Apr 2010

Permalink

May 20th, 2011

Re: Coding a Complete Binary Tree

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.

C Syntax (Toggle Plain Text)
                                                                      1(a)
 
                                            1(b)                                                   2(c)
 
                              21(d)                       1(e)                          2(f)                          1(g)
 
                        2(h)            1(i)           1(j)    9999(k)
                                                                      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)

Last edited by riazcp; May 20th, 2011 at 1:15 am.

riazcp

Reputation Points: 7

Solved Threads: 0

Newbie Poster

Offline

3 posts
since May 2011

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: Stupid Question

Next Thread in C Forum Timeline: computing the convex hull of a bunch of points

DaniWeb Message

Cancel Changes

User Name
Password