Difference between revisions of "TADM2E 5.7"
From Algorithm Wiki
(Created page with "Let's use the following tree for demonstration purposes: A B C D E F...") |
|||
| (9 intermediate revisions by 3 users not shown) | |||
| Line 21: | Line 21: | ||
It goes like this: | It goes like this: | ||
| − | 1. Use pre-order traversal to find root. (Beginning of tree/subtree) | + | 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) | + | 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) | + | 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: | So, our algorithm works like this: | ||
| − | Use pre-order traversal to find root > A | + | Use pre-order traversal to find root > A |
| − | Use in-order traversal to find left sub-tree > D B E | + | 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 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. | ||
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.
