Lecture 1 - Notes

January 4, 2016

Trees

Topological trees

• Free trees
• Rooted trees
• Ordered trees
• Binary trees

Free Trees

A free tree is the most general kind of tree.

definition: A free tree is an acyclic connected graph.

• Acyclic: No cycles
• Connected: There is a path between any two vertices

A free tree with $n$ nodes always has $e = n-1$ edges.

Example

How many trees are there with $n = 3$ vertices?

Solution

One. See above.

Rooted Trees

definition: A rooted tree is a tree in which some node is distinguished as the root.

Example

How many trees are there with $n = 4$ vertices?

Solution

Four. See above.

Ordered Trees

definition: An ordered tree is a rooted tree in which the subtrees are ordered recursively.

The tree is ordered "horizontally" (because that's how levels work).

Binary Trees

definition: A Binary Tree is either empty or consists of a root, a left subtree $L$ and a right subtree $R$ both of which are disjoint binary trees.

Example

How many trees are there with $n = 3$ vertices?

Solution

Five. See above.

Extended Binary Trees

definition: An Extended Binary Tree is either a leaf node or consists of a root, a left subtree $L$ and a right subtree $R$ both of which are disjoint extended binary trees.

• A binary tree where each node has two children called leaves
• A binary tree in which special nodes are added wherever a null subtree was present in the original tree so that each node in the original tree will always have 2 children (excluding an empty tree)

An Extended Binary Tree with $n$ internal nodes has $l = n + 1$ leaves.

Applications

• Binary Search Trees - Binary Tree
• Decision Trees - Extended Binary Tree

Representations

Binary Trees

Each node represented with a data value and left and right child nodes.

class Node {
    Object data;
    Node leftChild;
    Node rightChild;
}

Tree Traversal

Preorder

In-order

Postorder

Converting a Ordered Forest into a Binary Tree

1. Use the root of the ordered tree as the root of the binary tree
2. The leftmost node in the ordered tree becomes the left child of the parent node
3. Continue finding children of the parent node insert it as the right subtree of leftmost child
4. Repeat this process for all of the nodes
5. Nodes that have children in the ordered tree representation will have a left child in the binary tree representation
6. If a node has a right child in the binary tree representation it has siblings in the ordered tree representation