For this lab, you will write a program that will do a preorder, inorder, and postorder traversal of a graph stored as a left-middle-right child array representation. Specifically, the program should read in the number of nodes (no more than 10) in the graph, then read the left-middle-right child array representation, then print the three traversals. Note: The root of the tree will always be node 1. And again, that is mathematical numbering not C++ numbering. So you will need to subtract 1 from everything to store it properly, and then add 1 to print out.
Since the traversals are recursive, they should each be in their own function.
A sample run follows:
Please input the number of nodes: 7
Please input the left-middle-right child array representation of the graph:
2 0 4 3 5 6 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 The preorder traversal is: 1 2 3 5 6 7 4 The inorder traversal is: 3 2 5 6 7 1 4 The postorder traversal is: 3 5 7 6 2 4 1
BIG HINT: The algorithms are all on pages 514 and 515 in the book, and they are recursive. Because you are using an array instead of pointers, you will need to augment the algorithms to have the tree array as the parameter as well as the root index for the subtree you are working on. Additionally, you can replace the for loop with three calls since there are three children for each node. So for example, the preorder algorithm becomes:
Preorder(tree T, root r) //Writes the nodes of a tree with root r in preorder write(r) //remember to add one to the output since you subtracted one on input if there is a left child (i.e., T[r][0] is not -1) preorder(T,T[r][0]) if there is a middle child (i.e., T[r][1] is not -1) preorder(T,T[r][1]) if there is a right child (i.e., T[r][2] is not -1) preorder(T,T[r][2]) end Preorder