Chapter 11

Trees
Chapter Summary
Introduction to Trees
Applications of Trees
Tree Traversal
Spanning Trees
Minimum Spanning Trees
Section 11.1
Introduction to
Trees
Section Summary
Introduction to Trees
Rooted Trees
Trees as Models
Properties of Trees
Trees
Definition: A tree is a connected undirected graph with
no simple circuits.

Example: Which of
these graphs are trees?

Solution: G1 and G2 are trees - both are connected and have no

simple circuits. Because e, b, a, d, e is a simple circuit.
G3 is not a tree. G4 is not a tree because it is not connected.
Trees
Definition: A forest is a graph that has no
simple circuit, but is not connected. Each of the
connected components in a forest is a tree.
Trees (continued)

Theorem 1: An undirected graph is a tree

if and only if there is a unique simple path
between any two of its vertices.
Trees (continued)
Proof: Assume that T is a tree.
Then T is connected with no simple circuits.
Hence, if x and y are distinct vertices of T, there
is a simple path between them (by Theorem 1 of
Section 10.4). This path must be unique - for if
there were a second path, there would be a
simple circuit in T .
Hence, there is a unique simple path between
any two vertices of a tree.
Trees (continued)
Now assume that there is a unique simple path
between any two vertices of a graph T.
Then T is connected because there is a path
between any two of its vertices. Furthermore, T
can have no simple circuits since if there were a
simple circuit, there would be two paths between
some two vertices.
Hence, a graph with a unique simple path
between any two vertices is a tree.
Rooted Trees
Definition: A rooted tree is a tree in which one
vertex has been designated as the root and
every edge is directed away from the root.
An unrooted tree is converted into different
rooted trees when different vertices are chosen
as the root.
Rooted Tree Terminology
Terminology for rooted trees is a

mix from botany and genealogy

(such as this family tree

of the Bernoulli family of

mathematicians).
Rooted Tree Terminology
If v is a vertex of a rooted tree other than the
root, the parent of v is the unique vertex u
such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u.
Vertices with the same parent are called
siblings.
The ancestors of a vertex are the vertices in
the path from the root to this vertex, excluding
the vertex itself and including the root. The
descendants of a vertex v are those vertices
that have v as an ancestor.
Rooted Tree Terminology
A vertex of a rooted tree with no children is
called a leaf. Vertices that have children are
called internal vertices.
If a is a vertex in a tree, the subtree with a as
its root is the subgraph of the tree consisting
of a and its descendants and all edges
incident to these descendants.
Terminology for Rooted
Trees
Example: In the rooted tree T (with root a):
(i)Find the parent of c, the children of g, the
siblings of h, the ancestors of e, and the
descendants of b.
(ii)Find all internal vertices and all leaves.
(iii)What is the subtree rooted at G?
Solution:
(i)The parent of c is b. The children of g are h, i,
and j. The siblings of h are i and j. The ancestors of
e are c, b, and a. The descendants of b are c, d,
and e.
(ii)The internal vertices are a, b, c, g, h, and j. The
leaves are d, e, f, i, k, l, and m.
m-ary Rooted Trees
Definition: A rooted tree is called an m-ary tree if
every internal vertex has no more than m children.
The tree is called a full m-ary tree if every internal
vertex has exactly m children.
An m-ary tree with m = 2 is called a binary tree.
m-ary Rooted Trees
Example: Are the following rooted trees full m-ary
trees for some positive integer m?

Solution: T1 is a full binary tree because each of its

internal vertices has two children.
T2 is a full 3-ary tree because each of its internal vertices
has three children.
In T3 each internal vertex has five children, so T3 is a full 5-
ary tree.
T4 is not a full m-ary tree for any m because some of its
internal vertices have two children and others have three
Ordered Rooted Trees
Definition: An ordered rooted tree is a rooted
tree where the children of each internal
vertex are ordered.
We draw ordered rooted trees so that the
children of each internal vertex are shown in
order from left to right.
Ordered Rooted Trees
Definition: A binary tree is an ordered rooted
where where each internal vertex has at most
two children. If an internal vertex of a binary
tree has two children, the first is called the left
child and the second the right child. The tree
rooted at the left child of a vertex is called the
left subtree of this vertex, and the tree rooted
at the right child of a vertex is called the right
subtree of this vertex.
Ordered Rooted Trees
Example: Consider the binary
tree T.
(i) What are the left and right
children of d?
(ii) What are the left and right
subtrees of c?

Solution:
(i) The left child of d is f and the
right child is g.
(ii) The left and right subtrees of
c are displayed in (b) and (c).
b c
Trees as Models Arthur
Cayley
(1821-1895)
Trees are used as models in computer
science, chemistry, geology, botany,
psychology, and many other areas.

Trees were introduced by

in 1857 in his work counting

the mathematician Cayley

the number of isomers of

saturated hydrocarbons.
The two isomers of butane
are shown at the right.
Trees as Models
The organization of a computer file system into
directories, subdirectories, and files is
naturally represented as a tree.
Trees as Models
Trees are used to represent the
structure of organizations.
Properties of Trees
Theorem 2: A tree with n vertices has n − 1
edges.
Proof (by mathematical induction):
BASIS STEP: When n = 1, a tree with one vertex has no
edges. Hence, the theorem holds when n = 1.

k − 1 edges.
INDUCTIVE STEP: Assume that every tree with k vertices has

Suppose that a tree T has k + 1 vertices and that v is a leaf

of T.
Let w be the parent of v. Removing the vertex v and the

the inductive hypothesis, T′ has k − 1 edges. Because T has

edge connecting w to v produces a tree T′ with k vertices. By

one more edge than T′, we see that T has k edges.

2 、树的性质
定理 设 T 是非平凡图﹙ n,m﹚ ，则以下关于树的命题都是等价的：

① T 连通且无圈； 常用结论

② T 无圈且 m ＝ n-1 ；
③ T 连通且 m ＝ n-1 ；
④ T 无圈，但在 T 中任何二结点之间增加一条新边后有且仅有一个圈；
⑤ T 连通的，但删除 T 中的任意一条边后，便不连通； (n2)
⑥ T 中每一对结点之间有且仅有一条道路 (n2) 。

24
证明：
• 采用循环论证方法。
即只需证 1)2)3)4)5)6)1) 即可。
1)2) 用数学归纳法证明，对 n 作归纳。
当 n ＝ 2 时， m ＝ 1 ，显然有 m ＝ n-1 ；
假设当 n=k 时，命题成立；
当 n ＝ k+1 时，由于 T 连通而无圈，所以 T 中至少有一个度数为 1 的结点 v0.

在 T 中删去 v0 及其关联的边，便得到 k 个结点的连通而无圈的图，由归纳假设知它有 k-1 条边。

再将结点 v0 及其关联的边加回到原来的图中得到原图 T 。所以 T 中含有 k+1 个结点和 k 条

边，为此满足： m ＝ n-1 。

25
2)3)
设 T 有个分支 T1,T2, …,Tk, 则由 2) 知 , 每支 Ti 是无圈且连通的 (ni,mi) 图，

由 1)2) 知： mi=ni-1 因此

k k k
m   m i   ( ni  1)   ni  k n  k
i 1 i 1 i 1
∵m=n-1
∴k=1, 即 T 是连通的

26
5)6) （反证法）
由于 T 是连通的，因此 T 中任意二结点和之间都有道路。
若此道路不唯一，则 T 中含有回路，删去回路上的一条边， T 仍然是连通的，这就与 5 ）
矛盾。
所以此道路是唯一的。

27
推论 1 任意非平凡的树 T ＝ (n ， m) 中，至少有两片树叶。

证明：因树 T 是连通的，从而 T 中各结点的度数均大于等于 1 。设 T 中有 k 片树叶，其余结点

的度数均大于等于 2 。于是有
2m ＝ deg(v1)+deg(v2)+deg(v3)+……+deg(vn)
k+2(n-k) ＝ 2n-k 。
由于树中有 m ＝ n-1 ，于是有：
2(n-1)2n-k ，
由此可得： k2 。这就说明 T 中至少有两片树叶。■

28
Counting Vertices in Full m-Ary
Trees
Theorem 3: A full m-ary tree with i internal
vertices has n = mi + 1 vertices.

Proof : Every vertex, except the root, is the child

of an internal vertex. Because each of the i
internal vertices has m children, there are mi
vertices in the tree other than the root.
Hence, the tree contains n = mi + 1 vertices.
Counting Vertices in Full m-Ary
Trees (continued)

(i)n vertices has i = (n − 1)/m internal

Theorem 4: A full m-ary tree with

vertices and l = [(m − 1)n + 1]/m

leaves,
(ii) i internal vertices has n = mi +
1 vertices and l = (m − 1)i + 1
(iii)leaves,
l leaves has n = (ml − 1)/(m − 1)
vertices and i = (l − 1)/ (m − 1)
Proof (ofinternal
part i):vertices.
Solving for i in n = mi + 1 (from
Theorem 3) gives i = (n − 1)/m. Since each vertex is
either a leaf or an internal vertex, n = l + i. By solving

l = n − i = n − (n − 1)/m = [(m − 1)n +

for l and using the formula for i, we see that

1]/m.
Counting Vertices in Full
m-Ary Trees (continued)
Example: Suppose that someone starts a chain
letter. Each person who receives the letter is
asked to send it on to four other people. Some
people do this, but others do not send any
letters. How many people have seen the letter,
including the first person, if no one receives
more than one letter and if the chain letter
ends after there have been 100 people who
read it but did not send it out? How many
people sent out the letter?
Solution: 133 、 33
Level of vertices and height of
trees
When working with trees, we often want to have
rooted trees where the subtrees at each vertex
contain paths of approximately the same length.
To make this idea precise we need some
definitions:
 The level of a vertex v in a rooted tree is the length
of the unique path from the root to this vertex.
 The height of a rooted tree is the maximum of the
levels of the vertices.
Level of vertices and
height of trees
Example:
(i) Find the level of each vertex in
the tree to the right.
(ii) What is the height of the tree?
Solution:
(i) The root a is at level 0.
Vertices b, j, and k are at level 1.
Vertices c, e, f, and l are at level 2.
Vertices d, g, i, m, and n are at level 3.
Vertex h is at level 4.
(ii) The height is 4, since 4 is the largest level
of any vertex.
Balanced m-Ary Trees
Definition: A rooted m-ary tree of height h is
balanced if all leaves are at levels h or h − 1.

Example: Which of the rooted trees shown

below is balanced?

Solution: T1 and T3 are balanced, but T2 is not

because it has leaves at levels 2, 3, and 4.
The Bound for the Number of
Leaves in an m-Ary Tree

Theorem 5: There are at most mh leaves

in an m-ary tree of height h.
The Bound for the Number
of Leaves in an m-Ary Tree
Proof (by mathematical induction on height):
BASIS STEP: Consider an m-ary trees of height 1. The tree
consists of a root and no more than m children, all leaves.
Hence, there are no more than m1 = m leaves in an m-ary
tree of height 1.
INDUCTIVE STEP: Assume the result is true for all m-ary
trees of height < h. Let T be an m-ary tree of height h. The
leaves of T are the leaves of the subtrees of T we get when
we delete the edges from the root to each of the vertices
of level 1.
Each of these subtrees has height ≤ h− 1. By the inductive
hypothesis, each of these subtrees has at most mh− 1
leaves. Since there are at most m such subtees, there are
The Bound for the Number
of Leaves in an m-Ary Tree
Corollary 1: If an m-ary tree of height h has l
leaves, then h ≥ ⌈logm l⌉. If the m-ary tree is full
and balanced, then h = ⌈logm l⌉.