Class Notes (808,652)
CMPT 225 (60)
John Edgar (28)
Lecture

# CMPT 225 Week 9 Lecture 1

2 Pages
118 Views

School
Simon Fraser University
Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
Summer

Description
Traversals (+ recursion) void print(Node* nd) { if (nd != null) { print(nd->leftChild); cout << nd.data << endl; print(nd->right); } } In order traversal. How can you determine size with a traversal? Increment size as you traverse. At least 2 ways of doing this. 1st Way: // public wrapper function int size() const { return postOrderSize(root); // private function which does all the work } int postOrderSize(Node* nd) const { if (nd != null) { int left = postOrderSize(nd->leftChild); int right = postOrderSize(nd->rightChild); return left + right + 1; } return 0; // when reach null child, say nothing there (Base Case) } 2nd Way: Note: apparently this is broken int size() const { postOrderSize(root, 0); } int postOrderSize(Node* nd, int result) const { if (nd != null) { postOrderSize(nd->left, result); postOrderSize(nd->right, result); result++; } return result; } For a tree with n nodes, this will return 1. result is local to recursive call. What you do further down the tree has no impact on root's result. Re
More Less

Related notes for CMPT 225

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.