CSC148H5 Lecture Notes - Lecture 18: Longest Path Problem, Init, Arity
28 Feb 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) Lecture 18: binary trees 3 + n-ary trees. Maximum number of nodes in a binary tree of height h. height 0, max nodes is 1 height 1, max nodes is 3. Root 4, right child of root 5, left child root 6 height 2, max nodes is 7 height 3, max nodes is 15. List of lists: each list had an item, left list and right list. Nodes and references: each node had an item, left subtree, right subtree. But remember that not all trees are binary trees! How do we handle arbitrary ("n-ary") trees in our code. We will use a nodes and references representation. Left and right references are not going to work anymore. Instead, we will use a list of subtrees def __init__ (self: "tree", value: object =none, children: list =none): Our n-ary trees keep only the order of children, not their location.
