943,693 Members | Top Members by Rank

Software Development > C++ > how to print null subtree of a null subtree?
Ad:
  • C++ Discussion Thread
  • Marked Solved
  • Views: 3808
  • C++ RSS
You are currently viewing page 1 of this multi-page discussion thread
Permalink
Jan 6th, 2007
0

how to print null subtree of a null subtree?

Expand Post »
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...
Reputation Points: 11
Solved Threads: 0
Light Poster
sivaslieko++ is offline Offline
49 posts
since Dec 2006
Permalink
Jan 6th, 2007
0

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

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
Reputation Points: 11
Solved Threads: 0
Light Poster
sivaslieko++ is offline Offline
49 posts
since Dec 2006
Permalink
Jan 6th, 2007
0

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

Click to Expand / Collapse  Quote originally posted by sivaslieko++ ...
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.
Reputation Points: 84
Solved Threads: 15
Posting Whiz in Training
Ravalon is offline Offline
209 posts
since Dec 2006
Permalink
Jan 6th, 2007
0

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

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.
Reputation Points: 718
Solved Threads: 373
Nearly a Posting Maven
Lerner is offline Offline
2,253 posts
since Jul 2005
Permalink
Jan 7th, 2007
0

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

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...
Reputation Points: 11
Solved Threads: 0
Light Poster
sivaslieko++ is offline Offline
49 posts
since Dec 2006
Permalink
Jan 7th, 2007
0

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

Is it possible to see your full code for insertion and level order traversal.
Featured Poster
Reputation Points: 1536
Solved Threads: 431
Posting Expert
iamthwee is offline Offline
5,865 posts
since Aug 2005
Permalink
Jan 7th, 2007
0

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

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?
Featured Poster
Reputation Points: 1536
Solved Threads: 431
Posting Expert
iamthwee is offline Offline
5,865 posts
since Aug 2005
Permalink
Jan 7th, 2007
0

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

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... : (
Reputation Points: 11
Solved Threads: 0
Light Poster
sivaslieko++ is offline Offline
49 posts
since Dec 2006
Permalink
Jan 7th, 2007
1

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

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.
Featured Poster
Reputation Points: 1536
Solved Threads: 431
Posting Expert
iamthwee is offline Offline
5,865 posts
since Aug 2005
Permalink
Jan 7th, 2007
0

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

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
Reputation Points: 11
Solved Threads: 0
Light Poster
sivaslieko++ is offline Offline
49 posts
since Dec 2006

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

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.
Message:
Previous Thread in C++ Forum Timeline: Wow good book.
Next Thread in C++ Forum Timeline: graphics in c++





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC