need help with tree problem...

Posted on 2000-04-27
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.....
Question by:beachbumm
1 Comment
LVL 16

Accepted Solution

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

                  /  \
                 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:

         /  \
        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?


Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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 how to use strings and some functions related to them 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.

937 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

4 Experts available now in Live!

Get 1:1 Help Now