Exercise 3 Part A is understandable. I get what I'm supposed to do, which essential is the reverse of inorder and preorder. Unfortunately, I am at a road block with how to go about forming a tree.
It is obvious that the first piece of information to gather about the tree is the root. This can be done by getting the item at index 0 of preorder. So that should be the first element of the tree list. Next, you can find out which items are in the left subtree and which are in the right by finding that root's position in the inorder list.
For example, given preorder [10, 6, 8, 12, 15, 11] and inorder [8, 6, 12, 10, 11, 15] I can see that the root is 10 thanks to preorder. In inorder, it is clear that the left tree has six as the root with 8 and 12 as children, and the right tree has 15 as root with 11 as child. Thus, the resulting Tree List would be:
[10, [6, [8, None, None], [12, None, None]], [15, [11, None, None], [None, None, None]]]
The order of numbers in this tree list is exactly the same order as preorder gives them in. What is challenging is putting these numbers in tree list format, because a tree list's 2nd and 3rd elements are tree lists themselves unless they are none. What about a tree list with tons of children on one side? Something like [3, 8, 6, 12, 4, 10, 11, 15]? I am unsure of how to put that into a tree list format.
I feel like this exercise is going to take me as much time as the 2nd assignment, which is saddening.
No comments:
Post a Comment