C++ RSS C++ RSS

how to print null subtree of a null subtree?

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved
1 2 Last »

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

how to print null subtree of a null subtree?

 
0
  #1
Jan 6th, 2007
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...
Reply With Quote Quick reply to this message  
•
•
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?

 
0
  #2
Jan 6th, 2007
The actual tree structure is below:

C++ Syntax (Toggle Plain Text) 
  1.  
  2.              23
  3.             /  \
  4.           1     45
  5.             \    /  \
  6.              2  31 52
  7.               \   \
  8.                3  234
  9.                  \
  10.                   5
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2006
Posts: 209
Reputation: Ravalon is on a distinguished road 
Solved Threads: 15
Ravalon's Avatar
Ravalon Ravalon is offline Offline
Posting Whiz in Training

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

 
0
  #3
Jan 6th, 2007
•
•
•
•
Originally Posted by sivaslieko++ View Post
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.
C++ Syntax (Toggle Plain Text) 
  1. [-]
  2. [-][-]
  3. [-][-][-][-]
  4. [-][-][-][-][-][-][-][-]
  5. [-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
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.
[23]
[-][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[23]
[1][-]
[-][-][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[23]
[1][-]
[-][2][-][-]
[-][-][-][-][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[23]
[1][-]
[-][2][-][-]
[-][-][-][3][-][-][-][-]
[-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]

[23]
[1][-]
[-][2][-][-]
[-][-][-][3][-][-][-][-]
[-][-][-][-][-][-][-][5][-][-][-][-][-][-][-][-]

[23]
[1][45]
[-][2][-][-]
[-][-][-][3][-][-][-][-]
[-][-][-][-][-][-][-][5][-][-][-][-][-][-][-][-]

[23]
[1][45]
[-][2][31][-]
[-][-][-][3][-][-][-][-]
[-][-][-][-][-][-][-][5][-][-][-][-][-][-][-][-]

[23]
[1][45]
[-][2][31][-]
[-][-][-][3][-][234][-][-]
[-][-][-][-][-][-][-][5][-][-][-][-][-][-][-][-]

[23]
[1][45]
[-][2][31][52]
[-][-][-][3][-][234][-][-]
[-][-][-][-][-][-][-][5][-][-][-][-][-][-][-][-]
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.
Last edited by Ravalon; Jan 6th, 2007 at 8:27 pm.
It's hard to be humble when you're as gifted as I am at pretending to be an expert.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2005
Posts: 1,678
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 263
Lerner Lerner is offline Offline
Posting Virtuoso

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

 
0
  #4
Jan 6th, 2007
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.
Last edited by Lerner; Jan 6th, 2007 at 9:21 pm.
Reply With Quote Quick reply to this message  
•
•
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?

 
0
  #5
Jan 7th, 2007
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...
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

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

 
0
  #6
Jan 7th, 2007
Is it possible to see your full code for insertion and level order traversal.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

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

 
0
  #7
Jan 7th, 2007
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:
C++ Syntax (Toggle Plain Text) 
  1.               A
  2.              /
  3.             B     			 
  4.            / \
  5.           E   C
  6.           \  / \
  7.           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 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

C++ Syntax (Toggle Plain Text) 
  1. {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?
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
•
•
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?

 
0
  #8
Jan 7th, 2007
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... : (
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

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

 
1
  #9
Jan 7th, 2007
Just a quick example let's use the same tree

C++ Syntax (Toggle Plain Text) 
  1.              A
  2.              /
  3.             B     			 
  4.            / \
  5.           E   C
  6.           \  / \
  7.           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 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.
Last edited by iamthwee; Jan 7th, 2007 at 7:17 am.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
•
•
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?

 
0
  #10
Jan 7th, 2007
But B will occupy the array of index 2i+1 where http://www.daniweb.com/cgi-bin/mimetex.cgi?i 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
Reply With Quote Quick reply to this message  
Reply
1 2 Last »

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based beginner binary bitmap c++ c/c++ calculator char char* class code coding compile compiler console conversion count data database delete deploy developer dll download dynamiccharacterarray email encryption error file forms fstream function functions game getline givemetehcodez graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linker list loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference rpg sorting string strings struct temperature template text text-file tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC