Class Notes (1,100,000)
US (490,000)
Cornell (1,000)
CS (100)
CS 2110 (30)
Gries (30)
Lecture 12

CS 2110 Lecture Notes - Lecture 12: Binary Tree, Binary Search Algorithm, If And Only If


Department
Computer Science
Course Code
CS 2110
Professor
Gries
Lecture
12

This preview shows page 1. to view the full 5 pages of the document.
Lecture 12 - Trees
oTree 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)
oTree terminology
o
oFOREST!!!!
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version

Only page 1 are available for preview. Some parts have been intentionally blurred.

o
oBinary 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)
oApplications of Tree: syntax tree
Most languages have recursive, hierarchical structure
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.
A parser converts textual representations to AST
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version