322 Intermediate C Programming
(a) (b) (c) (d)
(e) (f) (g)
(h) (i) (j)
FIGURE 20.7: Insert values 8, 4, 11, 1, 9, 7, 10, 5, 12, 15.
Fig. 20.4 shows the tree after inserting two nodes. Since −504 is smaller than 917, the
second node is inserted to the left of the first node. This is an essential property of binary
search trees. Also, note that the root’s value (the address of the root node) does not change
after inserting the first node. In this example, the value remains 60000.
Fig. 20.5 shows that another tree node is inserted. The value is 1226 and it is larger
than 917. Thus, it is inserted to the right side of the first node. Fig. 20.6 shows a tree with
five tree nodes. The second view in (b) quickly becomes complicated as more nodes are
inserted. The memory view is also getting quite long. Thus, a different representation is
more convenient, as shown in Fig. 20.6 (d). In this view, each tree node is represented as an
oval. Note that “tree”s are drawn upside down, i.e., the root is at the top. This is different
from the trees seen in forests.
The values −504 and 73 are smaller than the value at root, so both tree nodes are at
the left side of root. Because 73 is larger than −504, 73 is at the right side of −504. Binary
search tree has an important property: For any tree node whose value is val, all tree nodes
on the left side have values smaller than val. Furthermore, all tree nodes on the right side
have values larger than val. Fig. 20.7 shows a binary search as values are inserted. The first
inserted value is the tree’s root.
The following code listing gives an implementation Tree insert, as well as an auxiliary
function TreeNode construct. It is static because it should not be called by any function
outside this file. When inserting a new value into a binary search tree, a new leaf node is
created. That means that the new node never has any children. Tree insert is similar to
the insert function in Section 19.1, where a linked list is used as a queue, and the newly
created node is placed at the end.
// tre einsert .c1
#in clude " tree .h "2
Binary Search Trees 323
#in clude < stdlib .h >3
s t a t i c TreeNode * T reeNo de_co nstru ct ( in t val )4
{5
TreeNode * tn;6
tn = malloc ( s i z e o f ( TreeNode )) ;7
tn -> left = NULL ;8
tn -> right = NULL ;9
tn -> value = val ;10
return tn;11
}12
13
TreeNode * Tree _ insert ( Tree N ode * tn , in t val )14
{15
i f ( tn == NULL )16
{17
// empty , create a node18
return Tr e eNod e _con s truc t ( val );19
}20
// not empty21
i f ( val == ( tn -> value ))22
{23
// do not insert the same value24
return tn;25
}26
i f ( val < ( tn -> value ))27
{28
tn -> left = Tree_i nsert ( tn -> left , val );29
}30
e l s e31
{32
tn -> right = T r ee_inser t ( tn -> right , val ) ;33
}34
return tn;35
}36
20.3 Searching a Binary Search Tree
To find whether a given number is stored in a binary search tree, the search function
compares the number with the value stored at the root. If the two values are the same, then
we know that the value is stored in the tree. If the number is greater than the value stored
at the root, then it is impossible to find the value on the left side of the tree. If the number
is smaller than the value stored at the root, then it is impossible to find the value on the
right side of the tree. This property is applied recursively until either (1) there is nothing
to search or (2) it is found. This is precisely why a binary search tree is called a binary -
search - tree: It is a tree that naturally supports searches. It is called binary search because
in each step, either the left subtree or the right subtree is discarded. In general, searching
binary search trees is far more efficient than searching linked lists. It is most efficient when
324 Intermediate C Programming
the left side and the right side of each node have the same number of nodes. In this case,
half of the search space is discarded after each comparison, because we no longer need to
consider half of the nodes in the tree. The following shows how to implement Tree search.
// tre esearch .c1
#in clude " tree .h "2
TreeNode * Tree _ search ( Tree N ode * tn , in t val )3
{4
i f ( tn == NULL )5
{6
// cannot find7
return NULL ;8
}9
i f ( val == ( tn -> value ))10
{11
// found12
return tn;13
}14
i f ( val < ( tn -> value ) )15
{16
// search the left side17
return Tree _ search ( tn -> left , val ) ;18
}19
return Tree _ search ( tn -> right , val ) ;20
}21
Note the similarities to the binary search over an array as described in Section 15.1. A
binary search tree is more flexible than a sorted array because a binary search tree supports
efficient insertion and deletion.
When I teach binary search trees, I always get this question: Why do we use binary
search trees (two links per node)? Why don’t we use ternary search trees (three links)? Or
quaternary search trees (4 links)? Earlier, I said the main problem of linked lists (one link
per node) is that finding a node needs to visit many nodes. Do binary search trees solve
this problem? Why?
There is a fundamental difference between one and two. For any positive number n, it is
possible to find a number k (maybe negative or irrational) such that 2
k
is n. For example,
if n is 0.5, k is −1. If n is 3.7, k is approximately 1.8875. If n is 191.6, k is approximately
7.5819. In contrast, one does not have this property. For any number m, 1
m
is still one.
What does this mean? It is possible to accomplish something by using two but it cannot be
accomplished by using one. The most important difference between linked lists and binary
trees is that the latter may discard large amounts of data very quickly. This is impossible if
only one link is used. For the same positive number n, it is possible to find another number
p such that 3
p
is n. Thus, two can do what three can do and vice versa. Moving from one
link (linked list) to two links (binary tree) is a fundamental improvement. However, moving
from two links to three (or four) links is not a fundamental improvement. Ternary search
trees can be better in some scenarios but there is no fundamental advantage.
Binary Search Trees 325
20.4 Printing a Binary Tree
Tree print can be implemented in three characteristically different ways. In each case,
the function has three steps:
(1) Visiting the node’s left side (subtree).
(2) Visiting the node’s right side.
(3) Printing the node’s value.
Visiting every node in a tree is also called traversing the tree. Every node is visited once,
and only once. There are 3! = 6 ways to order these three steps but (1) usually precedes
(2). Thus, the three ways to implement Tree print are:
• Pre-order traversal. The three steps are ordered as (3) → (1) → (2).
• In-order traversal. The three steps are ordered as (1) → (3) → (2).
For a binary search tree, in-order will print the values in the ascending order.
• Post-order traversal. The three steps are ordered as (1) → (2) → (3).
It is important to understand these three traversal methods, because each one is useful
in different circumstances, as will become apparent later in this book. The code listing below
shows an example of printing a tree using pre-order, in-order, and post-order traversals.
// tree print . c1
#in clude " tree .h "2
s t a t i c void TreeNo de_pri nt ( TreeNode * tn )3
{4
printf (" %d ", tn -> value );5
}6
7
s t a t i c void Tree_ print Preor der ( TreeN o de * tn )8
{9
i f ( tn == NULL )10
{11
return ;12
}13
Tree N ode_pr int ( tn );14
Tree _prin tPreo rder ( tn -> left );15
Tree _prin tPreo rder ( tn -> right ) ;16
}17
18
s t a t i c void Tree_ print Inord er ( TreeNode * tn )19
{20
i f ( tn == NULL )21
{22
return ;23
}24
Tree _prin tInor der ( tn -> left );25
Tree N ode_pr int ( tn );26
Tree _prin tInor der ( tn -> right );27
}28
29
s t a t i c void Tree _ prin tPost order ( TreeNode * tn )30
326 Intermediate C Programming
(a) (b) (c)
FIGURE 20.8: Three differently shaped binary search trees.
{31
i f ( tn == NULL )32
{33
return ;34
}35
Tree _pri n tPos torde r ( tn -> left );36
Tree _pri n tPos torde r ( tn -> right ) ;37
Tree N ode_pr int ( tn );38
}39
40
void Tree_pri n t ( T r eeNode * tn )41
{42
printf (" n n ===== Preorder ===== n ") ;43
Tree _prin tPreo rder ( tn );44
printf (" n n ===== Inorder ===== n ") ;45
Tree _prin tInor der ( tn ) ;46
printf (" n n ===== Postorder ===== n" );47
Tree _pri n tPos torde r ( tn ) ;48
printf (" n n") ;49
}50
Consider the different shapes of binary search trees in Fig. 20.8. How do the outputs
differ for each of the three traversal methods?
These three trees store the same values. They have different shapes due to the order of
insertion. In (a), 8 is inserted first. In (b), 11 is inserted first. In (c), 4 is inserted first. The
outputs of the three traversal methods are shown below.
(a) (b) (c)
pre-order 8 4 11 11 8 4 4 8 11
in-order 4 8 11 4 8 11 4 8 11
post-order 4 11 8 4 8 11 11 8 4
The pattern in in-order traversal is the easiest to see—the values are always visited
in the ascending order. In other words, this is a method of traversing the values in a
sorted ordering. Hence the name in-order traversal. One consequence of this is that in-order
traversal has the same outputs for the three differently shaped trees. Thus in-order traversal
cannot distinguish between different shapes of trees. In contrast, pre-order and post-order
traversals do distinguish the different shapes. If we want to describe the shape of a tree,
then in-order will not work. Pre-order and post-order traversals make this possible.
What are the outputs when printing with different traversal methods on the trees shown
in Fig. 20.9?
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.