Tree Traversal The purpose of tree traversal:visit (perform some operations on)each node in a tree systematically: Preorder traversal:the operations at a node are performed before(pre)its children are processed. Postorder traversal:the operations at a node are performed after (post)its children are processed. The operations on each node are performed recursively
Tree Traversal ◼ The purpose of tree traversal: visit (perform some operations on) each node in a tree systematically: ✓ Preorder traversal: the operations at a node are performed before (pre) its children are processed. ✓ Postorder traversal: the operations at a node are performed after (post) its children are processed. ◼ The operations on each node are performed recursively
Tree Traversal Example:Suppose the operation on each node is print the name of this node.Please give the outputs of the preorder and postorder traversals on the following tree. A B C D E F G H I J K L
Tree Traversal ◼ Example: Suppose the operation on each node is print the name of this node. Please give the outputs of the preorder and postorder traversals on the following tree. A B C D E H F G I J K L
Tree Traversal ■ Answer: Preorder traversal:A BFG C H KL D E I J Postorder traversal:F G BK L H C D I J E A
Tree Traversal ◼ Answer: ✓ Preorder traversal: A B F G C H K L D E I J ✓ Postorder traversal: F G B K L H C D I J E A
Tree Traversal ■ Example:Suppose A the operation on each node is print the name of this node.Please give B C the outputs of the preorder and E postorder traversals F G on the left tree. H K L
Tree Traversal ◼ Example: Suppose the operation on each node is print the name of this node. Please give the outputs of the preorder and postorder traversals on the left tree. A B C D L E F G I K H J