COMP 250 Lecture Notes - Lecture 18: Tree Traversal, The Algorithm, While Loop
27 Oct 2016
School
Department
Course
Professor
Document Summary
We are diving straight down to the bottom of the tree. Visit root for each child of root. Root is empty = base case. visit root = generally we will want to do with each node but we just leave it as this general case for now. For each child of the root, call the method recursively. So, we need a certain ordering of the children to know which one to go to first. This is called a preorder traversal, because whatever you do to each node, you do that before you make the recursive call. Starting at 1 (the main root), then you call recursively the children -- visit 2, call recursively, so visit 3, etc etc. When you get to 6, you have finished this subtree. Then go back to 1, since you"ve already called depthfirst first 2, now you do depth first for the second child. Visit implies that you do something at that node.
