Trees

Any connected graph without a cycle is called a *tree*. Every
edge of a tree is a bridge. In general, a graph without any cycles,
whether connected or not, is called a *forest*. We have already
seen some trees:

And many non-trees:

**Some Facts and Theorems about Trees**

- Now if
*u*and*v*are two vertices of a tree G. Then there is exactly one*u*-*v*path in G.

Proof of this is based on G being connected and having more than one path between the same two points would necessarily create a cycle in a connected graph. - Any tree that has more than one vertex has at least one vertex of
degree 1. (Lemma 10.5.1) Based on trees being finite and circuit free,
so there exists a
*u*-*v*path that terminates (consequently at a degree 1 vertex). - Any connected graph with
*p*vertices and*q*=*p*-1 edges is a tree. (Theorem 10.5.4) - Every tree with
*p*vertices has*q*=*p*-1 edges. (Theorem 10.5.2) - Any graph with
*p*vertices and fewer than*q*=*p*-1 edges is not connected and consequently, not a tree.

Some Definitions

A *rooted* tree has one vertex distinguished from the others.
This distinguished vertex is called the *root*. A vertex of a
tree is called a* leaf* if it has no children. Vertices that have
children are called* internal vertices.* The root is an internal
vertex unless it is the only vertex in the graph, in which case it is a
leaf. The *level* of a vertex is the number of edges (length) of
a path from the root to that vertex. The *height* of a rooted
tree is the maximum level of any of its vertices. Given an internal
vertex *v*, the children of *v* are all those vertices that
are adjacent to *v* and are one level farther away from the root
than *v*. If *w* is a *child* of *v*, then *v*
is called the *parent* of *w* and all other vertices in the
path from the root to *w* are *ancestors* of *w*,
while *w* is a *descendant* of each of these vertices.
Vertices with the same parent are called *siblings*.

Let T be a tree. If T has
only one or two vertices, then each is called a terminal vertex. If T has at least three vertices, then
a vertex of degree 1 in T is
called a terminal vertex (or a
leaf), and a vertex of degree
greater than 1 is called an internal
vertex (or a branch vertex).

*M-ary* Trees

An *m-ary* tree is a tree in which each vertex has *at most
m* children. The order in which the children are listed is
relevant. In particular, in a

**Full
and Complete Binary Trees
**

**Full binary tree:
** Each node is either a leaf or internal node with exactly two non
-empty children.

**Complete Binary Tree:
** If the height of the tree is

**Example ** For the following graph complete the following: The
root is ___. The left child of b is ____, while i is a _____ child of
h. The right subtree of g is ___&__, the left subtree of g is
___&___. Vertex i is a ________ of g, g is an _______ of i. The
height of this tree is _____. The root, a, is located at level __ and c
is located at level ___. There are eleven vertices and consequently
____ arcs in this tree. Vertices c and f are __________ of b and
___________ to each other.

**Two more Theorems**

- If
*k*is a positive integer and*T*is a full binary tree with*k*internal vertices, the*T*has a total of 2*k*+ 1 vertices and has*k*+ 1 terminal vertices. (Theorem 10.6.1 read proof on page 697) - A (complete) full binary tree of height
*h*has 2terminal vertices. Consequently, any binary tree of height^{h}*h*has at most 2terminal vertices,^{h}*t*. We have*t*£ 2, or equivalently lg^{h}*t*£*h*. (Theorem 10.6.2)

**Example **Is there a full binary tree with 5 internal vertices
and 6 terminal vertices? If so, how many total vertices does this tree
have?

Solution

**Example** Is there a binary tree with height 4 and 8 terminal
vertices? What is the greatest
possible number of terminal vertices in a binary tree of height 4?

Solution

One frequently has to perform operations on trees involving every
vertex. In order to perform the operation a recursive tree traversal is
required. There are three principal ways to traverse a tree: *preorder*,
*inorder*, and* postorder*.

Preorder: **NLR**

- (
**N**) Process the root. - (
**L**) Search the left subtree in preorder. - (
**R**) Search the right subtree in preorder.

Inorder: **LNR**

- (
**L**) Search the left subtree in inorder. - (
**N**) Process the root. - (
**R**) Search the right subtree inorder.

Postorder: **LRN**

- (
**L**) Search the left subtree in postorder. - (
**R**) Search the right subtree in postorder. - (
**N**) Process the root.

The essential difference is the order in which the root is processed: first, middle, or last.

To help with clarity of operation, consider a tree in which the root and internal vertices are arithmetic operators and the terminal vertices are variables:

What is the preorder traversal of this tree? *Solution*

What is the inorder traversal of this tree? *Solution*

What is the postorder traversal of this tree? *Solution*

Let m = 1 and n = 0.5 then determine the value of the expression found in your three solutions above.

**Example**

What are the preorder, inorder, and postorder expresions for the binary
tree in the *m-ary* example above?

*Solution*

Applet

http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html

*
*