主观题：Tree Traversals
Given the partial results of a binary tree's traversals in in-order, pre-order, and post-order. You are supposed to output the complete results and the level order traversal sequence of the corresponding tree.
### Input Specification:
Each input file contains one test case. For each case, a positive integer $$N$$ ($$\le 100$$) is given in the first line. Then three lines follow, containing the incomplete in-order, pre-order and post-order traversal sequences, respectively. It is assumed that the tree nodes are numbered from 1 to $$N$$ and no number is given out of the range. A - represents a missing number.
### Output Specification:
For each case, print in four lines the complete in-order, pre-order and post-order traversal sequences, together with the level order traversal sequence of the corresponding tree. The numbers must be separated by a space, and there must be no extra space at the beginning or the end of each line. If it is impossible to reconstruct the unique tree from the given information, simply print Impossible.
### Sample Input 1:
in
9
3 - 2 1 7 9 - 4 6
9 - 5 3 2 1 - 6 4
3 1 - - 7 - 6 8 -
### Sample Output 1:
out
3 5 2 1 7 9 8 4 6
9 7 5 3 2 1 8 6 4
3 1 2 5 7 4 6 8 9
9 7 8 5 6 3 2 4 1
### Sample Input 2:
in
3
- - -
- 1 -
1 - -
### Sample Output 2:
out
Impossible
### Grading Policy:
Chapter 1: Introduction (6 pts.)
Chapter 2: Algorithm Specification (12 pts.)
Chapter 3: Testing Results (20 pts.)
Chapter 4: Analysis and Comments (10 pts.)
Write the program (50 pts.) with sufficient comments.
Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
the cover page is not complete (-1)
the introduction is a simple copy + paste of the assignment statement (-3)
the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
the algorithm specification is not complete – the data structure description is missing (-2)
the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
not making one's algorithm easier to understand than a simple program (-2)
only a program + comments, which is not acceptable (-4)
others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
the document looks messy - some of the data in the charts and tables are missing (-1)
the hand-in is not zipped with proper folders (-1)
the hand-in is not complete - some files are missing (-1)
others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
the testing results contain some test cases, however with no specification on their purposes (-3)
the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
the programs are not working properly (-1 ~ -20)
the programs are not well-commented (-50)
the programming style is too messy to be judged (-1 ~ -5)
others - please specify in the final comments.
### Input Specification:
Each input file contains one test case. For each case, a positive integer $$N$$ ($$\le 100$$) is given in the first line. Then three lines follow, containing the incomplete in-order, pre-order and post-order traversal sequences, respectively. It is assumed that the tree nodes are numbered from 1 to $$N$$ and no number is given out of the range. A - represents a missing number.
### Output Specification:
For each case, print in four lines the complete in-order, pre-order and post-order traversal sequences, together with the level order traversal sequence of the corresponding tree. The numbers must be separated by a space, and there must be no extra space at the beginning or the end of each line. If it is impossible to reconstruct the unique tree from the given information, simply print Impossible.
### Sample Input 1:
in
9
3 - 2 1 7 9 - 4 6
9 - 5 3 2 1 - 6 4
3 1 - - 7 - 6 8 -
### Sample Output 1:
out
3 5 2 1 7 9 8 4 6
9 7 5 3 2 1 8 6 4
3 1 2 5 7 4 6 8 9
9 7 8 5 6 3 2 4 1
### Sample Input 2:
in
3
- - -
- 1 -
1 - -
### Sample Output 2:
out
Impossible
### Grading Policy:
Chapter 1: Introduction (6 pts.)
Chapter 2: Algorithm Specification (12 pts.)
Chapter 3: Testing Results (20 pts.)
Chapter 4: Analysis and Comments (10 pts.)
Write the program (50 pts.) with sufficient comments.
Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
the cover page is not complete (-1)
the introduction is a simple copy + paste of the assignment statement (-3)
the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
the algorithm specification is not complete – the data structure description is missing (-2)
the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
not making one's algorithm easier to understand than a simple program (-2)
only a program + comments, which is not acceptable (-4)
others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
the document looks messy - some of the data in the charts and tables are missing (-1)
the hand-in is not zipped with proper folders (-1)
the hand-in is not complete - some files are missing (-1)
others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
the testing results contain some test cases, however with no specification on their purposes (-3)
the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
the programs are not working properly (-1 ~ -20)
the programs are not well-commented (-50)
the programming style is too messy to be judged (-1 ~ -5)
others - please specify in the final comments.
