COMPSCI 61B Lecture Notes - Lecture 22: Tree Traversal, Infinite Loop, Planarity
Document Summary
A set of edges that connect those nodes. There is exactly one path between any 2 nodes. A rooted tree is a tree where we"ve chosen one node as the root . Every node n except the root has exactly one parent, defined as the first node on the path from n to the root. A node with no child is called a leaf. We"ve seen trees as nodes in a specific data structure implementation. Ex: sometimes you want to iterate over a tree. Suppose you want to find the total size of all files in a folder called cs61b. What one might call tree iteration is actually called tree traversal . Unlike lists, there are many orders in which we might visit the nodes. Each ordering is useful in different ways. Visit top to bottom, left to right: dbfaceg. Preorder: visit a node, then traverse its children. We trace a path around the graph, from the top going ccw.
