CS 225 Lecture Notes - Lecture 22: Tree Traversal

• School: University of Illinois
• Department: Computer Science
• Course: CS 225
• Professor: Heeren Cinda

Document Summary

// this is a traversal from bottom/right to the top. We have traversals that are so special that we give them names. Traversal is an idea of how to maneuver through the data structure. Traversals: a few discussion points template void binarytree::preorder(treenode * croot){ if(croot != null) { yell(croot->data); preorder(croot0>left); preorder(croot->right); by convention we always go left. The running time of a binary tree traversal is o(n) Work done is proportional to the # of nodes. 3 opportunities to yell is preorder public or private? preorder is private the tree nodes are private. // provide a way to access the treenode because we gave them a traversal that requests that data. // running time is o(n) by analogy w. traversal. // used in a copy constructor template treenode * binarytree::copy(treenode * croot) { // build new root treenode *t = null; if(croot != null) { t = new treenode(croot->data) // copy right t->right = copy(croot->right); return t;