C S 314 Lecture Notes - Lecture 7: Parsing, Branching Factor, Binary Tree
14 Dec 2016
School
Department
Course
Professor
Document Summary
Binary tree: contents and left and right links. Linked list: the first element contains the contents, the rest are a linked list of children. Implicit: a node may contain only the contents; the children can be generated from the contents or from the location of the parent. A node may not have a fixed number of children. Dedicating a large number of links would be wasteful if the average number of children is much smaller than the maximum, and it would still limit the possible number of children. Luckily, we can use the same structure as the binary tree, with just two links, and have unlimited children with no wasted space. We can think of a linked list as a tree. The first node of the list contains the contents of the node, and the rest of the list is a list of the children. The children, in turn, can be lists; a non-list is a leaf node.
