CS234 Lecture Notes - Tree Traversal, Binary Tree, Linked List
Document Summary
Cs 234 lecture 12, binary trees and heaps. Binary trees: representation of data that we can use, sometimes more effectively than, say, a. Left child (b is the left child of a) Right child (e is the right child of. Height (the number of levels height 4) o o. Depth (a is depth 0, f is depth 2) Ancestors (the ancestors of e are b and a) Descendants (the des. of c are f and h) Full binary tree every node has either zero or two children. Perfect binary tree all leaves are at the same level. Complete binary tree all levels besides the last are full, and the last o level has all nodes as far to the left as possible. Note: a perfect binary tree is both full and complete o o o. A perfect binary tree of height h has exactly 2h 1 nodes. A perfect tree of height 4 would have 15 nodes.