Chapter 6 Review
551
c H a p t e r 6 review
terminoloGy
acyclic graph (p. 482)
adjacency list (p. 494)
adjacency matrix (p. 492)
adjacent nodes (p. 481)
arc (edge) (p. 477, 478)
binary search tree (p. 534)
binary tree (p. 510)
binary tree search (p. 534)
bipartite complete graph (p. 483)
children nodes (p. 509)
complete binary tree (p. 510)
complete graph (p. 482)
connected graph (p. 482)
cycle (p. 482)
data compression (data
compaction) (p. 540)
data flow diagram (p. 480)
decision tree (p. 529)
degree of a node (p. 481)
depth of a node (p. 510)
depth (height) of a tree (p. 510)
directed graph (digraph) (p. 478)
endpoints (p. 478)
Euler’s formula (p. 488)
five-color theorum (p. 507)
forest (p. 510)
full binary tree (p. 510)
graph (p. 477, 478)
graph colorability (p. 506)
height of a tree (p. 510)
homeomorphic graphs (p. 491)
Huffman encoding (p. 542)
infix notation (p. 518)
initial point (p. 478)
inorder traversal (p. 515)
internal node (p. 510)
isolated node (p. 481)
isomorphic graphs (p. 485)
isomorphism (p. 486)
labeled graph (p. 479)
leaf (p. 510)
left child (p. 510)
length of a path (p. 482)
linked list (p. 494)
loop (p. 481)
loop-free graph (p. 481)
map-coloring problem (p. 506)
node (vertex) (p. 477, 478)
nonrooted (free) tree (p. 509)
null pointer (p. 495)
optimal algorithm (p. 533)
parallel arcs (p. 481)
parent node (p. 509)
path (pp. 482, 483)
planar graph (p. 487)
Polish notation (p. 518)
postfix notation (p. 518)
postorder traversal (p. 515)
prefix code (p. 541)
prefix notation (p. 518)
preorder traversal (p. 514)
reachable node (p. 483)
reverse Polish notation
(RPN) (p. 518)
right child (p. 510)
root of a tree (p. 509)
simple graph (p. 481)
sparse matrix (p. 494)
subgraph (p. 482)
terminal point (p. 478)
tree (p. 509)
tree traversal (p. 514)
weighted graph (p. 479)
Self-teSt
Answer the following true–false questions.
section 6.1
1. A connected graph has an arc between any two
nodes.
2. If graph G 1 is isomorphic to graph G 2 , then a node
of degree 5 in G 1 will be mapped to a node of degree 5 in G 2.
3. No matter how a planar graph is drawn, its arcs will
intersect only at nodes.
4. If part of the adjacency list representation of a
graph contains
2
3
4
then node 2 is adjacent to node 3 and node 3 is
adjacent to node 4.
5. The adjacency matrix of a directed graph is not
symmetric.
section 6.2
1. The depth of any node in a tree is less than or equal
to the height of the tree.
2. Because a tree is a graph, a complete tree is also a
complete graph.
3. In the left child–right child array representation of
a binary tree, any row of the array that corresponds
to a leaf will have all zero entries.
4. Postorder traversal of an expression tree results in
an algebraic expression in reverse Polish notation.
5. In preorder tree traversal, the root is always the first
node visited.
551
c H a p t e r 6 review
terminoloGy
acyclic graph (p. 482)
adjacency list (p. 494)
adjacency matrix (p. 492)
adjacent nodes (p. 481)
arc (edge) (p. 477, 478)
binary search tree (p. 534)
binary tree (p. 510)
binary tree search (p. 534)
bipartite complete graph (p. 483)
children nodes (p. 509)
complete binary tree (p. 510)
complete graph (p. 482)
connected graph (p. 482)
cycle (p. 482)
data compression (data
compaction) (p. 540)
data flow diagram (p. 480)
decision tree (p. 529)
degree of a node (p. 481)
depth of a node (p. 510)
depth (height) of a tree (p. 510)
directed graph (digraph) (p. 478)
endpoints (p. 478)
Euler’s formula (p. 488)
five-color theorum (p. 507)
forest (p. 510)
full binary tree (p. 510)
graph (p. 477, 478)
graph colorability (p. 506)
height of a tree (p. 510)
homeomorphic graphs (p. 491)
Huffman encoding (p. 542)
infix notation (p. 518)
initial point (p. 478)
inorder traversal (p. 515)
internal node (p. 510)
isolated node (p. 481)
isomorphic graphs (p. 485)
isomorphism (p. 486)
labeled graph (p. 479)
leaf (p. 510)
left child (p. 510)
length of a path (p. 482)
linked list (p. 494)
loop (p. 481)
loop-free graph (p. 481)
map-coloring problem (p. 506)
node (vertex) (p. 477, 478)
nonrooted (free) tree (p. 509)
null pointer (p. 495)
optimal algorithm (p. 533)
parallel arcs (p. 481)
parent node (p. 509)
path (pp. 482, 483)
planar graph (p. 487)
Polish notation (p. 518)
postfix notation (p. 518)
postorder traversal (p. 515)
prefix code (p. 541)
prefix notation (p. 518)
preorder traversal (p. 514)
reachable node (p. 483)
reverse Polish notation
(RPN) (p. 518)
right child (p. 510)
root of a tree (p. 509)
simple graph (p. 481)
sparse matrix (p. 494)
subgraph (p. 482)
terminal point (p. 478)
tree (p. 509)
tree traversal (p. 514)
weighted graph (p. 479)
Self-teSt
Answer the following true–false questions.
section 6.1
1. A connected graph has an arc between any two
nodes.
2. If graph G 1 is isomorphic to graph G 2 , then a node
of degree 5 in G 1 will be mapped to a node of degree 5 in G 2.
3. No matter how a planar graph is drawn, its arcs will
intersect only at nodes.
4. If part of the adjacency list representation of a
graph contains
2
3
4
then node 2 is adjacent to node 3 and node 3 is
adjacent to node 4.
5. The adjacency matrix of a directed graph is not
symmetric.
section 6.2
1. The depth of any node in a tree is less than or equal
to the height of the tree.
2. Because a tree is a graph, a complete tree is also a
complete graph.
3. In the left child–right child array representation of
a binary tree, any row of the array that corresponds
to a leaf will have all zero entries.
4. Postorder traversal of an expression tree results in
an algebraic expression in reverse Polish notation.
5. In preorder tree traversal, the root is always the first
node visited.