Trees
We can impose some further restrictions on digraphs to create trees
A tree:
is a connected digraph
has exactly one node with in-degree = 0, called the root
may have other nodes, but if so, then each node has an in-degree = 1
No restriction on out-degree
Trees (cont.)
Nodes with an out-degree = 0 are called leaves (or terminal vertices)
Other nodes are called interior nodes (or nonterminal vertices)
These restrictions mean that trees have some graph properties, and lack others
Examples on p. 403
Paths?
Trees (cont.)
Because of how we have defined a tree, each destination node is the root of another tree, called a subtree
A node by itself is a tree
We can define the depth of a tree to be the length of the longest path - p. 404
The level of a node is the length of the path from the root to the node
Trees (cont.)
The destination vertices are called children
The source vertex is called the parent
Children of the same parent are called siblings
All vertices reachable from a given vertex are called descendants
In order for trees to be useful, we store some data, called the key or value, at each node
Tree Terminology Review
Root
Leaf/Terminal vs. Interior/Nonterminal
Subtree
Depth
Level
Parent, Child, Sibling, Descendant
Binary Trees
If we impose further restrictions, we can define a class of trees called Binary Trees
These help us describe and manipulate many structures in computer science
A binary tree
is a tree whose nodes have out-degrees <= 2
has subtrees that are ordered, such that the values in the left subtree < the values in the right subtree
Binary Trees (cont.)
A strictly binary tree is one where the out-degree of every vertex is 2 (or 0)
A binary tree is said to be balanced if it is not “heavy” on either side
There are different definitions for “heavy” depending on the application
For us, “heavy” means that the depth of one side is greater than the depth of the other side by more than 1 (unbalanced) - p. 406
Implementing Binary Trees
We could use the graph implementation, because trees are just special graphs
However, we can take advantage of the the fact that we know we are using binary trees to create a more-optimal structure
Each vertex will be a linked node, with a key field, a left-subtree pointer, and a right-subtree pointer
Binary Tree Nodes
TYPE InfoType IS …; -- some type
TYPE BinaryTreeNode;
TYPE Tree is ACCESS BinaryTreeNode;
TYPE BinaryTreeNode IS RECORD
  Key   : InfoType;
  Left  : Tree;
  Right : Tree;
END;
p. 408
Traversing Binary Trees
Recall we looked at preorder, inorder, and postorder traversals
We will rename these: NLR, LNR, and LRN traversal
N is Node
L is Left child
R is Right child
Traversing Binary Trees (cont.)
Because these trees are recursively defined (i.e., each subtree is also a tree), implementation is really straightforward
We use the familiar Visit routine to process a node
NLR Traversal
PROCEDURE Traverse_NLR( T : Tree ) IS
BEGIN
  IF T = NULL THEN
    RETURN;
  END IF;
  Visit( T );              -- N
  Traverse_NLR( T.Left );  -- L
  Traverse_NLR( T.Right ); -- R
END Traverse_NLR;
LNR Traversal
PROCEDURE Traverse_LNR( T : Tree ) IS
BEGIN
  IF T = NULL THEN
    RETURN;
  END IF;
  Traverse_LNR( T.Left );  -- L
  Visit( T );              -- N
  Traverse_LNR( T.Right ); -- R
END Traverse_LNR;
LRN Traversal
PROCEDURE Traverse_LRN( T : Tree ) IS
BEGIN
  IF T = NULL THEN
    RETURN;
  END IF;
  Traverse_LRN( T.Left );  -- L
  Traverse_LRN( T.Right ); -- R
  Visit( T );              -- N
END Traverse_LRN;
Examples:
Examples:
Examples:
Examples:
Expression Trees
Recall that we use:
Single-letter identifiers
One-digit integer constants
The operators:   +  -  *  /

Examples:
A - B
Examples:
A
Examples:
( A - B ) + c
Examples:
A - ( B + C )
Examples:
( A + B ) * ( C - D )
Examples:
A + B * C
Examples:
A / B - c
Examples:
A + B - C + D
Examples:
A - ( B + C ) * D
Traversals
A - ( B + C )
Operations on Binary Search Trees (BST)
Imposing these ordering constraints on binary trees makes searching easier
Inserting is more complex
p. 421
Deleting is even more complex
p. 428-430
Finite-State Machines
There are many situations, especially in computer science, where we can represent (or process) things in a state-driven manner
Given a current state, we can transition to a new state based on the next input
Lexical analysis of source code
Syntax checking for compilers
Process transitions in operating systems
Lexical Analyzers
Given an alphabet and a grammar, we can determine whether a string is contained in a given “language”
Lexical Analyzers (cont.)
Alphabet: ‘a’ & ‘b’
Grammar:

Input Strings:
abababb
ababaab
bbbb
Lexical Analyzers (cont.)
Alphabet: ‘a’, ‘b’, ‘c’ & ‘d’
Grammar:


Input Strings:
adabbcb
abbbccbd
adacccbba
Parser
We can use a lexical analyzer for grabbing key words from source code
Read a word, check if it is in our language of legal “tokens”
Then, we can run a sequence of tokens through a higher-level grammar, that understands computer language syntax
This is called parsing