Welcome to Lesson 11!Learning ObjectivesBy the end of today's class, you should know...- How to trace recursive tree traversals on a BST:
- inOrder
- preOrder
- postOrder
- How to write the above 3 methods
- How the method call stack is used to produce the correct output
1. Tree Traversals1.1 Tree Traversal Introduction- Traversals define an ordering for which we can "visit" each element in a structure to perform operations such as printing.
- With linear structures, such as a linked lists, the order in which to visit each value is evident.
- However, for trees, there is no obvious ordering of the nodes.
- There are many possible ways to visit each node in a BST.
- We will examine 3 options:
- pre order
- post order
- in order
- In
your Lab, you will be asked to write preOrderPrint, inOrderPrint and
postOrderPrint, which each define a means of printing BSTs according to the ordering defined by the traversals.
- These recursive methods are simple to write.
- Their names come from when the root of each subtree is visted.
- Is it visited before the recursive calls (preorder)?
- Is it visited after the recursive calls (postorder)?
- Is it visited between the recursive calls (inorder)?
- What do you think the Big-O runtime of these methods is?
- O(n) Why?
- Let's get an introduction to this topic by watching this video
- Below is the pseudocode for each of the methods.
- Note that these methods would be the "helper" versions in our implementation
Pseudocode for inOrderPrint(root)1. If the root is NULL a. return; 2. Otherwise a. Call inOrderPrint recursively on the root's leftchild b. Print the data at the root c. Call inOrderPrint recursively on the root's rightchild Pseudocode for preOrderPrint(root)1. If the root is NULL a. return 2. Otherwise a. Print the data at the root b. Call preOrderPrint recursively on the root's leftchild c. Call preOrderPrint recursively on the root's rightchild Pseudocode for postOrderPrint(root)1. If the root is NULL a. return 2. Otherwise a. Call postOrderPrint recursively on the root's leftchild b. Call postOrderPrint recursively on the root's rightchild c. Print the data at the root 1.2. Tree Traversal Examples- Let's trace the printing order of the three algorithms on the same binary tree
**inOrderPrint:**
**preOrderPrint:**
**postOrderPrint:**
1.3. Reflection: Tracing Tree Traversals and Writing the Methods- Find a piece of paper
- Using the examples above, trace inOrderPrint, preOrderPrint and postOrderPrint on the BST below.
- Now, write the 3 recursive print methods, along with their helper methods.
Wrap Up- Answer the review questions on Canvas for today's lesson
Upcoming Assignments**Lab due Monday****Study for your Quiz**
~Have a Great Day!~ |