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...
The actual tree structure is below:
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 "-"
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.
[[B]23[/B]]
[-][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][-]
[-][[B]2[/B]][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][-]
[-][[B]2[/B]][-][-]
[-][-][-][[B]3[/B]][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][-]
[-][[B]2[/B]][-][-]
[-][-][-][[B]3[/B]][-][-][-][-]
[-][-][-][-][-][-][-][[B]5[/B]][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][[B]45[/B]]
[-][[B]2[/B]][-][-]
[-][-][-][[B]3[/B]][-][-][-][-]
[-][-][-][-][-][-][-][[B]5[/B]][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][[B]45[/B]]
[-][[B]2[/B]][[B]31[/B]][-]
[-][-][-][[B]3[/B]][-][-][-][-]
[-][-][-][-][-][-][-][[B]5[/B]][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][[B]45[/B]]
[-][[B]2[/B]][[B]31[/B]][-]
[-][-][-][[B]3[/B]][-][234][-][-]
[-][-][-][-][-][-][-][[B]5[/B]][-][-][-][-][-][-][-][-]
[[B]23[/B]]
[[B]1[/B]][[B]45[/B]]
[-][[B]2[/B]][[B]31[/B]][[B]52[/B]]
[-][-][-][[B]3[/B]][-][[B]234[/B]][-][-]
[-][-][-][-][-][-][-][[B]5[/B]][-][-][-][-][-][-][-][-]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.
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.
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...
Is it possible to see your full code for insertion and level order traversal.
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 DA 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 2^h - 1 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 2i+1, and its right child at 2i+2. 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?
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... : (
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 positionsOk let us consider the node F. We know F is on the right hand side of E.
So by our rule F will occupy the array of index 2i+2 where i will obviously be 3. Because that's the position where E was in our array.
Thus... 2*3 +2=8
Therefore F must occupy index 8. And of course it does.
You just go through each level of the tree as you build the array.
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
Incorrect, my example is complete and without error.
Do you want me to go through anther example?
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 ;)
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 positionsLet 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.
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
Well once you have populated your array you could use the following code to print it.
In my array the number -1 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!
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. ;)
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..
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 5So 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.
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.
thanks a lot for everything iamthwee, but I am almost out of mind. I could not make it. I think I should give up :(
thanks a lot for everything iamthwee, but I am almost out of mind. I could not make it. I think I should give up :(
Don't give up!
I have a complete working version right here which I have written myself using my method.
So I CAN guarantee you it does work.
I don't just want to post it however, because you're sooo close.
Like I said read over my examples and apply it to your example.
:p
Should I continue to use Queue method or should I completely change it with array method?
While using Queue I stored the pointers to values stored in the tree into the queue and called these values like "p->item" and store each subnode into queue with below code:
if(p->left!=NULL)
myQ.Qinsert(p->left);
if(p->right!=NULL)
myQ.Qinsert(p->right);But in array method, you store values not pointers into array so I could not call the left subtrees as Queue method? What should I do....
Sory I tire you a bit iamthwee : (
Use my array example. Yes. You don't need the queue anymore.
Do you want me to explain how to use it with your example.
pleaseee
23
/ \
1 45
\ / \
2 31 52
\ \
3 234
\
5First of all we need to find out how much space to allocate for our array. This is simply 2^h - 1 Where h is the tree height or number of levels. In your case it is 2^5-1 = 31.
int array[32]Now we initialise all those to -1 . Remember we have defined -1 to be null.
for (int i=0; i <32; i++)
{
array[i] = -1;
}Now we use 23 1 45 2 31 52 3 234 5 and start of from left to right inserting each number into our array.
For example 23 is the root so say array[0]=23 Now we move on to 1. From our tree 1 is to the left of 23. So 2i+1 = 2*0+1 = 1 Therefore array[1]=1 Now we move onto 45. From our tree 45 is on the right of 23. So 2i+2 = 2* 0+2 = 2 Therefore array[2] =45 Now move onto 2. From our tree 2 is on the right of 1. So 2i+2 = 2*1+2 =4 Therefore array[4]=2 Now move onto 31. From our tree 31 is to the left of 45. So 2i+1=2*2+1=5 Therefore array[5]=31 .
And so on.
Once you have finished filling the entire array. Print it out using my code I have provided before.
hi iamthwee at this point I could not achieve tree traversal I think there is something necessary related with recursion. How did you travers the tree? Could you please explain?
My code is below:
void BST::BreadthFirstTraversal(){
BSTNode *p=root;
int myArray[32];
for(int i = 0; i<32;i++){
myArray[i]=-1;
}
int m;
if(root!=NULL){
myArray[0] = root->item;
while(m<sizeof(myArray)){
if(p->left!=NULL){
myArray[2*m+1] = p->left->item;
}
if(p->right!=NULL){
myArray[2*m+2] = p->right->item;
}
}
}
for(int t = 0; t<32;t++){
cout<<myArray[t];
}
}I make it :) Thanks a lot :)
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.