Welcome! Log In Create A New Profile

Advanced

Ass04: Q1(b)

Posted by 34898425 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Ass04: Q1(b)
July 17, 2006 08:22PM
Hi guys;

I am really struggling with this question. Did any of you manage to get the same BST for both given traversals. I've done it a few dozen times now and come up with the same solution- meaning different BST's for each traversal. I've even tried to simulate the BST's in Mathematica but thats no help. Any ideas or suggestions?
Thanks

Regards
Re: Ass04: Q1(b)
July 19, 2006 08:24PM
Are you still struggling? Can help if you want. Email me at gordonb@trenstar.co.za
avatar Re: Ass04: Q1(b)
July 21, 2006 08:51PM
Think of it logically, in a Pre-order traversal, the first node visited is the root and the last visited is the right-most leaf. Thus the root in this case is A. And M is a leaf on the right-hand branch from the root.

In an in-order traversal, the left branch is visited first, then the node itself then the right branch is visited. Knowing that A is the root, you can divide the in-order print out into the left branch and right branch with A in the middle. You can also tell that because it keeps going left, left, left, left, etc. until it reaches a NULL, you know that the first node printed out is the left-most node and the last node printed out is the right-most node.

From all of this you should have: A is the root, C is the left-most node and it may or may not have a right branch but does not have a left branch, and that L is the right-most node but M is the right-most leaf. Thus M is the left branch of L and L doesn't have a right branch.

You can break the tree up into smaller sections (ie. left of root, and right of root) and follow this same logic until you have the complete structure.

The easiest way is to iterate:

PO : ABCDEFGHIJKLM
IN : CEDFBAHJIKGML

The first node is the root in the PO list. The IO list show the left/right split.

PO : A | BCDEF | GHIJKL
IN : CEDFB | A | HJIKGML

Now just take one branch and do the same thing again.

PO : BCDEF
IN : CEDFB

The first node in PO is the root. The IO shows the layout of the left/right split.

PO : B | CDEF |
IO : CEDF | B |

This shows that there is not right branch to B.

-----------------------------------------------
You keep breaking it up until you've used up all the nodes in the left branch and the you start on the right branch
Sorry, only registered users may post in this forum.

Click here to login