COMP 2140 Lecture 13: 10_17_tree.pdf
13 Aug 2014
School
Department
Course
Professor
Document Summary
A tree consists of: a set of nodes a set of edges connecting pairs of nodes. Exactly one path between any two nodes path: connected sequence of edges. Each node c (except the root) has one parent p, the first node on the path from c to the root c is called p child. Non-leaf(internal) node: a node with one or more children. Ancestors of a node d: nodes on the path from d to the root, including d itself. If a is an ancestor of d, d is a descendant of a. Length of a path: numbers of edges in the path. Depth of a node n: length of the path from n to root (depth of root is 0) Nodes with the same depth form a level of the tree. Height of a node n: length of the path from n to its deepest descendant (height of any leaf node is 0)
