Difference between revisions of "TADM2E 5.7"
From Algorithm Wiki
(Undo revision 412 by GreatSalmon (talk)) |
(Undo revision 411 by GreatSalmon (talk) The counter example is not correct. Note the question here is "pre-order and in-order" not post-order) |
||
| Line 63: | Line 63: | ||
Use post order to find right subtree > null | Use post order to find right subtree > null | ||
Use pre order to find parent of C > A | Use pre order to find parent of C > A | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Revision as of 01:58, 9 June 2016
Let's use the following tree for demonstration purposes:
A
B C
D E F
G H
Pre-order traversal: A B D E C F G H
In-order traversal: D B E A C G F H
Post-order traversal: D E B G H F C A
Part A.
We create a recursive algorithm that processes sub trees until we arrive at single leaf nodes.
It goes like this:
1. Use pre-order traversal to find root. (Beginning of tree/subtree)
2. Use in-order traversal to find left sub tree (All nodes before root)
2a. Process left sub tree if not leaf node
3. Use in-order traversal to find right sub tree (All nodes after root)
3a. Process right sub tree if not leaf node
So, our algorithm works like this:
Use pre-order traversal to find root > A
Use in-order traversal to find left sub-tree > D B E
Use pre-order traversal to find root > B
Use in-order traversal to find left sub-tree > D
Use in-order traversal to find right sub-tree > E
Use in-order traversal to find right sub-tree > C G F H
Use pre-order traversal to find root > C
Use in-order traversal to find left sub-tree > null
Use in-order traversal to find right sub-tree > G F H
Use pre-order traversal to find root > F
Use in-order traversal to find left sub-tree > G
Use in-order traversal to find right sub-tree > H
B. For pre & post order, the algorithm works like this.
1. Use post-order to find left most leaf. (first node)
2. Use pre order to find parent. (node preceding result 1)
3. Use post order to find right child. (Between left child and parent)
3a. Process right subtree if not leaf node
4. Return to step 2 to find parent of parent node.
So....
Use post-order to find left-most leaf > D
Use pre order to find parent > B
Use post order to find right child > E
Use pre-order to find parent of B > A
Use post order to find right subtree > G H F C
Use post order to find leftmost leaf > G
Use pre-order to find parent > F
Use post order to find right subtree > H
Use pre order to find parent of F > C
Use post order to find right subtree > null
Use pre order to find parent of C > A
