Class Notes (834,976)
Canada (508,836)
CSC148H1 (92)
Paul Gries (18)


1 Page
Unlock Document

Computer Science
Paul Gries

Tree  A tree has a set of nodes and a set of edges that connect the nodes  properties: o Each node has exactly one parent. Except the root, which has none o There is a path from the root to every node o There are no cycles: no paths that form loops  Definitions: o Leaf: a node with no children o Internal node: a node that is neither a leaf nor the root o Siblings: nodes with the same parent o Subtree: the tree formed from a node together with all its descendants and the edges among them o Branching factor: the maximum number of children for any node o Path: a sequence of nodes. If m1 is the parent of m2, m2 is the parent of m3, …, and mk-1 is the parent of mk, then the sequence of nodes m1, m2, …, mk is a path in the tree  The length of such a path is k, i.e. the number of nodes on the path o Height of a tree: the length of the longest path from the root to a leaf o Depth of a node: the number of edges on the path from the root to that n
More Less

Related notes for CSC148H1

Log In


Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.