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

feb06c.docx

1 Page
147 Views
Unlock Document

Department
Computer Science
Course
CSC148H1
Professor
Paul Gries
Semester
Winter

Description
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


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit