Page 187 - DCAP407_DATA_STRUCTURE

Data Structure

In figure 10.3, the graph (i) has two different, unconnected set of nodes. Graphs can also contain cycles.
Graph (ii) has several cycles. One such path is from x1 to x2 to x4 and back to x1. Another one is from x1
to x2 to x3 to x5 to x4 and back to x1. (There are also cycles in graph (ii).) Graph (iii) does not have any
cycles and all nodes are reachable. Therefore, it is a tree.

Did you know? Programs like Microsoft MapPoint that can generate driving directions from one city
to another, use graphs, where the modeling cities are represented as nodes in a graph
and the roads connecting the cities as edges.
Trees can be represented as graphs.

Figure 10.4 represents a tree, which is a non-linear representation of data.

Figure 10.4: A Tree Structure

Let us now discuss some of the common terminologies used with respect to trees.
Root Node
The root of a tree is called a root node. In figure 10.4, A is the root node. A root node occurs only once in
the whole tree.
Parent Node

The parent of a node is the immediate predecessor of that node. In the figure 10.4, A is the parent node
of B and C, B is the parent node of D, and C is the parent node of E, F and G. G is the parent node of H.
Child Node

Child nodes are the immediate successors of a node.
In the figure 8.4, B and C are the child nodes of A, D is the child node of B; E, F, and G are the child
nodes of C and finally, H is the child node of G.
Leaf Node
A node which does not have any child nodes is known as a leaf node. In figure 10.4, D, E, F and H are
the leaf nodes.
Link
The pointer to a node in the tree is known as a link. A node can have more than one link. In figure 10.4,
node A has two links. Node C has three links. Nodes B and G have only one link and nodes D, E, F and
H have no links.

180 LOVELY PROFESSIONAL UNIVERSITY