Page 17 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The left part represents the information part of the node, which may contain an entire record of
data items (e.g. NAME, ADDRESS,...). The right part represents the Next pointer field of the
node, and there is an arrow drawn from it to the next node in the list. This follows the usual
practice of drawing an arrow from a field to a node when the address of the node appears in the
given field.

Notes The pointer of the last node contains special value, called the null pointer, which is
any invalid address.

1.3.5 Tree

A tree is an acyclic, connected graph. A tree contains no loops or cycles. The concept of tree is one
of the most fundamental and useful concepts in computer science. Trees have many variations,
implementations and applications. Trees find their use in applications such as compiler
construction, database design, windows, operating system programs, etc. A tree structures is
one in which items of data are related by edges.

Example: A very common example is the ancestor tree as given in Figure 1.4. This tree
shows the ancestors of KUMAR. His parents are RAMESH and RADHA. RAMESH’s parents are
PADMA and SURESH who are also grand parents of KUMAR (on father’s side); RADHA’s parents
are JAYASHRI and RAMAN who are also grand parents of KUMAR (on mother’s side).
Figure 1.4: A Family Tree

Kumar

Radha Ramesh

Jayashri Raman Padma Suresh

Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf

1.3.6 Graph

All the data structures (Arrays, Lists, Stacks, and Queues) except Graphs are linear data structures.
Graphs are classified in the non-linear category of data structures. A graph G may be defined as
a finite set V of vertices and a set E of edges (pair of connected vertices). The notation used is as
follows:
Graph G = (V,E)

10 LOVELY PROFESSIONAL UNIVERSITY