CS 2110 Lecture Notes - Lecture 12: Binary Tree, Binary Search Algorithm, If And Only If
14 Jun 2017
School
Department
Course
Professor
Document Summary
Lecture 12 - trees: tree overview. Tree: data structure with nodes, similar to a linked list. Each node may have zero or more successors (children) Each node has exactly one predecessor (parent), except the root, which has none. All nodes are reachable from the root. Binary tree: tree in which each node can have at most two children (left and right children: tree terminology o, forest!!! o, binary vs general tree. In binary tree each node has two pointers: left and right. One or both could be null, meaning they are empty. In a general tree, a node can have any number of child nodes (and they are not needed to be ordered: applications of tree: syntax tree. This structure is implicit in ordinary textual representation. Recursive structure can be made explicit by representing sentences in the language as trees: abstract syntax trees (ast) Asts are easier to optimize, generate code from, etc.
