how to print null subtree of a null subtree?

[sivaslieko++]

Hi everybody,
for example I have such a tree in c++:

23
/ \
1 45
\ / \
2 31 52
\ \
3 234
\
5

I can print this tree in this way by using breadthFirst-level method:

23,
1, 45
2, 31, 52
3, 234
5

But how can I print this tree like this:

23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

At the last two line it is necessary to print null subtree of a null subtree by "-"

Please help me...

[sivaslieko++]

The actual tree structure is below:

23
            /  \
          1     45
            \    /  \
             2  31 52
              \   \
               3  234
                 \
                  5

[Ravalon]

But how can I print this tree like this:

23 1,45 -,2 | 31,52 -,- | -,3 | -,- | -,234 -,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,- At the last two line it is necessary to print null subtree of a null subtree by "-"

My first go at it would be to mirror any old tree traversal with a sparse matrix that's sized to assume a full tree. If the height of the tree is 5, like your example, the sparse matrix would be initialized to a null subtree character and look like this.

[-]
[-][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

Then you do say an inorder traversal on the tree and also use cursors for the matrix that match the same position in the tree. You want the updates to look like this.

[<strong>23</strong>]
[-][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][-]
[-][<strong>2</strong>][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][-]
[-][<strong>2</strong>][-][-]
[-][-][-][<strong>3</strong>][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][-]
[-][<strong>2</strong>][-][-]
[-][-][-][<strong>3</strong>][-][-][-][-]
[-][-][-][-][-][-][-][<strong>5</strong>][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][<strong>45</strong>]
[-][<strong>2</strong>][-][-]
[-][-][-][<strong>3</strong>][-][-][-][-]
[-][-][-][-][-][-][-][<strong>5</strong>][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][<strong>45</strong>]
[-][<strong>2</strong>][<strong>31</strong>][-]
[-][-][-][<strong>3</strong>][-][-][-][-]
[-][-][-][-][-][-][-][<strong>5</strong>][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][<strong>45</strong>]
[-][<strong>2</strong>][<strong>31</strong>][-]
[-][-][-][<strong>3</strong>][-][234][-][-]
[-][-][-][-][-][-][-][<strong>5</strong>][-][-][-][-][-][-][-][-]

[<strong>23</strong>]
[<strong>1</strong>][<strong>45</strong>]
[-][<strong>2</strong>][<strong>31</strong>][<strong>52</strong>]
[-][-][-][<strong>3</strong>][-][<strong>234</strong>][-][-]
[-][-][-][-][-][-][-][<strong>5</strong>][-][-][-][-][-][-][-][-]

Print the matrix and you're done! :) At a glance, I don't see any problems with the logistics and the code should be pretty simple. But I can't say for sure unless I try it myself.

[Lerner]

Like Ravalon I've never done this before either. My thought would be if you aren't comfortable developing sparse arrays you might be able to mimic the sparse array protocol proposed using a full binary tree of the same height as the original tree instead.

To do this I'd first determine the length of the longest path in the original tree, which should be the same as the height of the original tree. Then I'd use the height of the original tree to develop a full binary tree of the same height, setting each node to a default value. Then I'd traverse the original tree and copy the values of each node in the original tree into the respective nodes of the full binary tree. Lastly, I'd do a level order traversal of the full binary tree printing out a hyphen if the value of the node is the default value and the non default value of the node if it's not the default value.

[sivaslieko++]

Thanks Ravalon but I do not know anything about matrix :((

Also Thanks Larner too but I could not understand some points. What can be the default value? And how can I copy each value properly?

I am a bit novice please help me...

[iamthwee]

Is it possible to see your full code for insertion and level order traversal.

[iamthwee]

If each node in a tree contains exactly two references, the tree is called a binary tree. Because reference can be null, each node in a binary tree can have 0, 1, or 2 successor nodes. Example:

A
             /
            B     			 
           / \
          E   C
          \  / \
          F G   D

A binary tree is full if all of its leaves are on the same level, and all internal nodes have exactly two children. A full binary tree with height h has [tex]2^h - 1[/tex] nodes. A binary tree is complete if all the "holes" are on the right side of the deepest level.

A binary tree can also be stored in an array in the following way: first, put the root in index 0, then, for every node in index i, put its left child at [tex]2i+1[/tex], and its right child at [tex]2i+2[/tex]. In this way, the above binary tree will be represented as

{A, B, _, E, C, _, _, _, F, G, D}

The "_" in the array is a special value indicating nonexistent values, or "holes". The holes of course will be "null". If the binary tree is complete, then there is no "hole" when it is stored in an array between nodes.

Does that give you any ideas?

[sivaslieko++]

thanks iamthwee,
but i can not produce the output:
23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

by using the array you have just explained, or i could not exactly what you said... : (

[iamthwee]

Just a quick example let's use the same tree

A
             /
            B     			 
           / \
          E   C
          \  / \
          F G   D

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

Ok let us consider the node [tex]F[/tex]. We know [tex]F[/tex] is on theright hand side of [tex]E[/tex].

So by our rule [tex]F[/tex] will occupy the array of index [tex]2i+2[/tex] where [tex]i[/tex] will obviously be [tex]3[/tex]. Because that's the position where E was in our array.

Thus... [tex]2*3 +2=8[/tex]

Therefore [tex]F[/tex] must occupy index [tex]8[/tex]. And of course it does.

You just go through each level of the tree as you build the array.

[sivaslieko++]

But B will occupy the array of index 2i+1 where [IMG]http://www.daniweb.com/cgi-bin/mimetex.cgi?i[/IMG] will obviously be 1 so index B will be 3 Because that's the position where A was in our array. But in your example its index was 1.
Also in this I could not print null subtree of null subtree?

Please help meee

[iamthwee]

Incorrect, my example is complete and without error.

Do you want me to go through anther example?

[sivaslieko++]

Yes iamthwee it would be super:confused: !!! Could you please explain your method on my example:
My tree is below:

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

So sory :sad: 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 ;)

[iamthwee]

Another example.

A
             /
            B     			 
           / \
          E   C
          \  / \
          F G   D

{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 [tex]E[/tex]. We know [tex]E[/tex] is on theleft hand side of node [tex]B[/tex].

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

Thus [tex] 2*1+1 = 3[/tex]

[tex]E[/tex] occupies position [tex]3[/tex]. Which it does.

[sivaslieko++]

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

[iamthwee]

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

In my array the number [tex]-1[/tex] represents null.

#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

23
1,45
-,2|31,52|
-,-|-,3|-,-|-,234|
-,-|-,-|-,-|-,5|-,-|-,-|-,-|-,-

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

[Ravalon]

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

[sivaslieko++]

hi iamthwee, my function to print is below:

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.

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

[iamthwee]

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.

23 1 45 2 31 52 3 234 5

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

Now establish what the parent node of [tex]1[/tex] is and whether [tex]1[/tex] 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.

[iamthwee]

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.

[sivaslieko++]

thanks a lot for everything iamthwee, but I am almost out of mind. I could not make it. I think I should give up :(