Difference between revisions of "TADM2E 5.7"
From Algorithm Wiki
(Remove the incorrect algo for part B) |
|||
| Line 47: | Line 47: | ||
1) | 1) | ||
| − | + | A | |
| − | + | / \ | |
| − | D | + | B C |
| + | / | ||
| + | D | ||
2) | 2) | ||
| − | + | A | |
| − | + | / \ | |
| − | + | B C | |
| + | \ | ||
| + | D | ||
In tree 1, D is the left child of B. In tree 2, D is the right child of B. For both trees, the traversals are: | In tree 1, D is the left child of B. In tree 2, D is the right child of B. For both trees, the traversals are: | ||
Latest revision as of 21:39, 17 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. I have a counterexample. Consider both following trees:
1)
A / \ B C / D
2)
A
/ \
B C
\
D
In tree 1, D is the left child of B. In tree 2, D is the right child of B. For both trees, the traversals are: Pre-order: A B D C Post-order: D B C A
So there is no way of rebuilding a unique tree from these two traversals.
