Solved

need help with tree problem...

Posted on 2000-04-27
1
190 Views
Last Modified: 2010-04-15
after spending some time working on this and maybe coming up with the answer i need some help...what tree does the sequence of statements produce in post-order? binTreeClass S; S.SetRootdata(10); S.AttachLeft(9, Success); S.AttachRight(8,Success); S.LeftSubTree().AttachLeft(2,Success);S.LeftSubTree().LeftSubTree().AttachLeft(3,Success);S.LeftSubTree().LeftSubTree().AttachRight(5,Success);S.RightSubTree().AttachLeft(7,Success);S.RightSubTree().AttachLeft(6,Success);

i think the answer is 10,9,2,3,5,8,7,6

also what tree does the sequence of statements produce for T in post-order using the binary Tree S above?

R.SetRootdata(20); R.AttachLeft(1,Success); R.AttachRight(30,Success);
binTreeClass T(4,R,S);

assuming the answer is 4,20,10,30,10,9,2,3,5,8,7,6

need help.....
0
Comment
Question by:beachbumm
1 Comment
 
LVL 16

Accepted Solution

by:
imladris earned 20 total points
ID: 2756035
The tree appears to wind up like this:

                   10
                  /  \
                 9    8
                /    / \
               2    7  (6)
              / \
             3   5

I'm not sure where the 6 goes. The phrase S.RightSubTree().AttachLeft(6,success) appears to plunk it ontop of the 7. For the sake of continueing I'll assume there was a typo there and that it should have been AttachRight.

Now, the traversal of a tree involves checking if the current node is a leaf, traversing the left subtree, then the right subtree. The difference between pre-order, in-order and post-order lies in when you access/print/show the data. In post-order the data is shown last. So, first we go down the left subtree. That repeats till we get to 3. This is a leaf, traversing the left and right subtree produces nothing so then 3 is shown. Now we go back up to 2. We now first have to traverse its right subtree, which is a leaf so we show 5. Now we show 2 (having done its left and right subtrees). Then back up to 9 (with no right subtree) then to 10. 10 cannot be shown yet, first we have to traverse its right subtree, this leads us down to 7, then 6, then 8 then 10. So assuming I have the 6 in the right spot the answer is:

3, 5, 2, 9, 7, 6, 8, 10

The answer you showed looks like the in-order traversal of the tree, where the data is shown between the traversal of the left and right subtrees (which would put 6 in the spot I assumed).

As for the next question, the tree R would appear to be:

          20
         /  \
        1    30

and I'm guessing that the statement binTreeClass T(4,R,S) means that T is a new tree with a root node of 4, a left subtree consisting of R and a right subtree of S. If that's correct a post-order traverse would be:

1, 30, 20, 3, 5, 2, 9, 7, 6, 8, 10, 4

How are my guesses holding up this time?


0

Featured Post

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Problem to show menu 5 88
An API detour question 7 84
How to copy documents folder to network folder automatically as backup? 15 86
What is sub-make ? 2 58
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question