DaniWeb Forum Index > Software Development > C++

how to print null subtree of a null subtree?

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#11

Jan 7th, 2007

Incorrect, my example is complete and without error.

Do you want me to go through anther example?

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 49

Reputation: sivaslieko++ is an unknown quantity at this point

Solved Threads: 0

sivaslieko++ sivaslieko++ is offline

Offline

Light Poster

Re: how to print null subtree of a null subtree?

#12

Jan 7th, 2007

Yes iamthwee it would be super

!!! Could you please explain your method on my example:
My tree is below:

Name: tree.JPG
Views: 9
Size: 2.3 KB

And the output have to be like this:
23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

So sory

but I could not understand how can I print "-" for example in the last line "-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-" properly for all null subtrees by using your method.

Thanks a lot for your concern

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#13

Jan 7th, 2007

Another example.

Help with Code Tags

C++ Syntax (Toggle Plain Text)

Help with Code Tags

(Toggle Plain Text)

{A, B, _, E, C, _, _, _, F, G, D} 
 |  |  |  |  |  |  |  |  |  |  |
 0  1  2  3  4  5  6  7  8  9  10 <-index positions

Let us consider the node $E$ . We know $E$ is on the left hand side of node $B$ .

So by our rule $E$ will occupy the array of index $2i+1$ where $i$ will obviously be $1$ since that where $B$ was as an index position in our array.

Thus $2*1+1 = 3$

$E$ occupies position $3$ . Which it does.

Last edited by iamthwee; Jan 7th, 2007 at 8:57 am.

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 49

Reputation: sivaslieko++ is an unknown quantity at this point

Solved Threads: 0

sivaslieko++ sivaslieko++ is offline

Offline

Light Poster

Re: how to print null subtree of a null subtree?

#14

Jan 7th, 2007

Yes I understood in this time thanks but I actually want to know how to print all null nodes as "-" under the right subtree of root A. But in your example just there are 4 subtree showed. Actually I could not understand this point

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#15

Jan 7th, 2007

Well once you have populated your array you could use the following code to print it.

In my array the number $-1$ represents null.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
 
using namespace std;
 
int main()
{
    int array[]={23,1,45,-1,2,31,52,-1,-1,-1,3,-1,-1,-1,234,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1,-1};
 
 
    for ( int i = 0; i < 31; i++ )
    //31 = 2^5 -1 (array max size)
    {
        if (i > 3)
        {
          if (i % 2 !=0)
          {
            cout<<"|";
          }
        }
 
       if ( i > 1 )
       { 
        if (i % 2 ==0)
        {
          cout << ",";
        }
       }
        //i.e 2^i (you could make this part less hard coded
        if(i==1-1 || i ==2-1 || i==4-1 || i==8-1 || i==16-1 || i==32-1)
        {
          cout << "\n";
        }
        if (array[i] == -1 )
        {
          cout << "-"; 
        }
        else
        {
          cout << array[i];
        }
    }  
    cin.get();
}
#include <iostream>

using namespace std;

int main()
{
    int array[]={23,1,45,-1,2,31,52,-1,-1,-1,3,-1,-1,-1,234,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1,-1};
    
   
    for ( int i = 0; i < 31; i++ )
    //31 = 2^5 -1 (array max size)
    {
        if (i > 3)
        {
          if (i % 2 !=0)
          {
            cout<<"|";
          }
        }
          
       if ( i > 1 )
       { 
        if (i % 2 ==0)
        {
          cout << ",";
        }
       }
        //i.e 2^i (you could make this part less hard coded
        if(i==1-1 || i ==2-1 || i==4-1 || i==8-1 || i==16-1 || i==32-1)
        {
          cout << "\n";
        }
        if (array[i] == -1 )
        {
          cout << "-"; 
        }
        else
        {
          cout << array[i];
        }
    }  
    cin.get();
}

My output

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
 
23
1,45
-,2|31,52|
-,-|-,3|-,-|-,234|
-,-|-,-|-,-|-,5|-,-|-,-|-,-|-,-
23
1,45
-,2|31,52|
-,-|-,3|-,-|-,234|
-,-|-,-|-,-|-,5|-,-|-,-|-,-|-,-

I've just tried it with your example and it works!

Last edited by iamthwee; Jan 7th, 2007 at 10:03 am.

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 209

Reputation: Ravalon is on a distinguished road

Solved Threads: 15

Ravalon

Offline

Posting Whiz in Training

Re: how to print null subtree of a null subtree?

#16

Jan 7th, 2007

•

Originally Posted by sivaslieko++

Thanks Ravalon but I do not know anything about matrix (

A huge part of programming is researching things you don't fully understand. Not knowing anything isn't an excuse not to try, especially with the beautiful resource of the internet at your fingertips.

If it makes the concept easier, just think of a matrix as a 2D array. Now you know a lot about matrices, and if you don't, you're probably not ready for binary trees.

It's hard to be humble when you're as gifted as I am at pretending to be an expert.

•

Join Date: Dec 2006

Posts: 49

Reputation: sivaslieko++ is an unknown quantity at this point

Solved Threads: 0

sivaslieko++ sivaslieko++ is offline

Offline

Light Poster

Re: how to print null subtree of a null subtree?

#17

Jan 7th, 2007

hi iamthwee, my function to print is below:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
void BST::BreadthFirstTraversal(){
 Queue myQ;
 BSTNode *p;
 int myDepth = 0;
 cout<<endl;
 if(root!=NULL){
  myQ.Qinsert(root);
  while(!myQ.QEmpty()){
 
   p = myQ.QDelete();
   cout<<p->item<<" ";
 
   if(p->left!=NULL)
    myQ.Qinsert(p->left);
   if(p->right!=NULL)
    myQ.Qinsert(p->right);
  }
 }
}
void BST::BreadthFirstTraversal(){
 Queue myQ;
 BSTNode *p;
 int myDepth = 0;
 cout<<endl;
 if(root!=NULL){
  myQ.Qinsert(root);
  while(!myQ.QEmpty()){
   
   p = myQ.QDelete();
   cout<<p->item<<" ";

   if(p->left!=NULL)
    myQ.Qinsert(p->left);
   if(p->right!=NULL)
    myQ.Qinsert(p->right);
  }
 }
}

this will produce this output:

23 1 45 2 31 52 3 234 5

when I insert the code below to , it exits the program without any output or error.

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
 
   if(p->left==NULL){
    int y = -1;
    BSTNode * temp = new BSTNode(y);
    myQ.Qinsert(temp);
   }
   if(p->right==NULL){
    int y = -1;
    BSTNode * temp = new BSTNode(y);  
    myQ.Qinsert(temp);
   }
 
   if(p->left==NULL){
    int y = -1;
    BSTNode * temp = new BSTNode(y);
    myQ.Qinsert(temp);
   }
   if(p->right==NULL){
    int y = -1;
    BSTNode * temp = new BSTNode(y);  
    myQ.Qinsert(temp);
   }

How can I insert -1 to form an array like yours..

Last edited by WaltP; Jan 7th, 2007 at 2:17 pm. Reason: Please start using CODE tags. See BBCODEs post in the Announcements

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#18

Jan 7th, 2007

•

How can I insert -1 to form an array like yours..

You have to use the method I showed you before to insert your numbers in the array.

It's good that you have your level order traversal algo working though because that will be useful.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
23 1 45 2 31 52 3 234 5
23 1 45 2 31 52 3 234 5

So you need to first add $23$ to your array at index position [0]

Now establish what the parent node of $1$ is and whether $1$ is on the left hand side or right hand side of the parent.

Carry on untill you have populated your array.

You might need a little time to think about this. Keep going you've almost got it, just keep reading over my examples.

Last edited by iamthwee; Jan 7th, 2007 at 10:47 am.

*Voted best profile in the world*

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#19

Jan 7th, 2007

Oh you don't actually insert -1 into the array at all.

You initialise your entire array to -1 and then just overwrite each valid number you encounter.

*Voted best profile in the world*