The Essentials Of Computer Organization And Architecture 4th Edition by Linda Null,Julia Lobur

تمرين 8

Most books concerning algorithms and data structures present traversal algorithms as recursive procedures. (Recursive procedures are subroutines or functions that call themselves.) However, the computer achieves this recursion using iteration! The algorithm below uses a stack to perform an iterative preorder traversal of a tree. (Refer to exercise 8.) As each node is traversed, its key value is printed as in the diagram above.
a) Modify the algorithm so that it will perform an inorder traversal.
b) Modify the algorithm so that it will perform a postorder traversal. (Hint: As you leave a node to follow its left subtree, update a value in the node to indicate that the node has been visited.)
Reference of Exercise 8:
A graph traversal is the act of interrogating (or visiting) every node in the graph. Traversals are useful when nodes are added to a tree in a certain order (perhaps random) and retrieved in some other given order. Three frequently used traversals, preorder, inorder, and postorder, are shown in the diagram below, with diagram (a) illustrating a preorder traversal, (b) an inorder traversal, and (c) a postorder traversal.
a) Rearrange the tree above so that a preorder traversal will print the node key values in alphabetical order. Change only the key values in the nodes. Do the same for an inorder traversal.
b) Perform the other two traversals on both of the trees redrawn in exercise 8a.