Solved

need help with tree problem...

Posted on 2000-04-27
1
183 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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

706 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now