Section 5.4 Introduction to Trees

SECTION 5.4 Introduction to Trees

Definitions

Tree	A graph is called a tree, if, and only if, it doesn't contain a circuit and it is connected.
Trivial tree	A graph that consists of a single vertex is called a trivial tree.
Empty tree	A tree that does not have any vertices or edges is an empty tree.
Terminal vertex	Let t be a tree. A vertex of degree 1 in t is called a terminal vertex or a leaf.
Internal vertex	Let t be a tree. A vertex of degree greater than 1 in t is called an internal vertex or a branch vertex.

Other tree properties:

For any positive integer n, any tree with n vertices has n - 1 edges.
For any positive integer n, if G is a connected graph with n vertices and n - 1 edges, then G is a tree.

For the following graph:

This graph is a tree, since it does not contain any circuits and it is connected.
Vertices v₅, v₆, v₈, v₉, v₁₀ and v₁₁ are all leaves (terminal vertices) of this tree.
Vertices v₀ to v₄, and v₇, are all internal vertices of this tree.
This tree has 12 vertices and 11 edges.

Exercise: Determine which of the following graphs are trees and which are not.

There are many situations in which trees arise. Some common examples include:

1. Family Trees

2. Molecular Structures

Hydrocarbon Molecule

3. Algebraic Expression Trees

expression : (x - y) + z

Rooted Trees

Rooted tree	A rooted tree is a tree in which one vertex is distinguished from the other vertices and is called the root.
Level	The level of a vertex is the number of edges along the unique path between it and the root.
Height	The height of a rooted tree is the maximum level to any vertex of the tree.
Children	Given any internal vertex v of a rooted tree, the children of v are all those vertices that are adjacent to v and are one level father away from the root than v.
Parent	If w is a child of v of a rooted tree, then v is called the parent of w.
Siblings	If two vertices are children of the same parent, then these two vertices are called siblings.
Ancestor	Given vertices v and w, if v lies on the unique path between w and the root, then v is an ancestor of w.
Descendant	Given vertices v and w, if v lies on the unique path between w and the root, then w is a descendant of v.

A rooted tree is illustrated in the following diagram.

Binary Trees

Binary tree	A binary tree is a rooted tree in which every internal vertex has at most two children.
Left and right children	Each child in a binary tree is either a left child or a right child, and each internal vertex has at most one left and one right child.
Full binary tree	A full binary tree is a binary tree in which each internal vertex has exactly two children.
Left and right subtrees	Given an internal vertex v of a binary tree T, the left subtree of v is the binary tree whose root is the left child of v, whose vertices consist of the left child of v and all its descendants, and whose edges consist of all those edges of T that connect the vertices of the left subtree together. The right subtree of v is defined analogously.

Other properties:

If n is a positive integer and T is a full binary tree with n internal vertices, then T has a total of 2n + 1 vertices and has n + 1 terminal vertices.
If T is a binary tree that has t terminal vertices and height h, then t < 2^h.

For the following binary tree:

Take a chapter quiz.
Go to Class Agenda.