Miss.Rohini A. Shinde Notes
Introduction To Data Structure
Introduction to data structure
Introduction:
Data structures are used in almost every program or software
system. Specific data structures are essential ingredients of many efficient
algorithms, and make possible the management of huge amounts of data, such as
large databases and internet indexing services. Some formal design methods and
programming languages emphasize data structures, rather than algorithms, as the
key organizing factor in software design.
Data:
Data are simply values or set of values.
A data item refers
to a single unit of values.
Data item that are divided into sub items are called group items; those which are not are called
elementary items. Computer science is concerned with study of data which
involves
Machine
that hold the data.
Technologies
used for processing data.
Methods
for obtaining information from data.
Structure for representing data.
Data are
simply values or sets of values.A data item refers to a single unit of
values.Data items that are devided into subitems are called as GROUP tem.
Data items
which are not devided into subitems are called as ELEMENTARY item.
For
example:
Name of
students can be devided into three subitems are first name,middle name and last
name.So name is a GROUP item.
The Pin
code can not be devided into subitems therefore is called as Elementary items.
Information:
Raw data is of little value in its present form unless it is
organized into a meaningful format. If we organize data or process data so that
it reflect some meaning then this meaningful or processed data is called
information.
Data type:
Data type is a term used to describe information type that can
be processed by a computer system and which is supported by a programming language.
More formally we define the data type as “ a term which refers to the kind of
data that a variable may take in “. Several different types of data can be
processed by a computer system e.g. Numeric data, text data, video data, audio
data, spatial data etc. A brief classification of data types is as shown in
fig.
Data type
Built in or primary User defined
Derived
int,
Enumeration,
Array
real,
union
Function
char,
structure
Pointer
Boolean
class
void,
pointer
Data
Structure: Data
structure is a particular way of storing and organizing data in a computer so
that it can be used efficiently. When we define a data structure we are in fact
creating a new data type of our own i.e. using predefined types or previously
user defined types. The basic types of data structure includes : files, lists,
arrays, trees etc. Different kinds of data structures are suited to different
kinds of applications, and some are highly specialized to specific tasks. The
choice of a particular data structure for an application depends upon two
factors:
1.
Structure must reflect the actual relationship of the data in the real world.
2. The structure should be simple enough so that one can
efficiently process the data when necessary.
Classification of Data Structure: Data structures are normally classified into two categories:
1. Primitive Data Structure: Primitive data structure are native to machine‟s hardware. Some
primitive data structure are
· Integer
· Character
· Real Number
· Logical Number
· Pointer
2.
Nonprimitive Data Structure: These
type of data structure are derived from the primitive data structures. Some non
primitive data structures are
· Array
· List
· Files
· Tree
· Graph
Entity: An entity is something that has certain attributes or properties
which may be assign values,The values can be numeric or non numeric.
For
example: Employee of an organization is an entity.
The
attributes associated with this entity are employee number,name age, sex
address,etc.
Every
attributes has certain value.The collection of all entities form an entity
set.All the employees in an organization forms entity set.
The term
Information is also used for data with given attributes.Information means
meaningful data.
Field is single elementary unit of information reprenting an attribute
of entity.
For
example:
Name,age,sex
are all fields.
Record: A record is s collection of fields values of a given entity.
i.e.one record for one employee.
File: A fileis s collection of records of entities . i.e.collection of
records of all employesss form a file.
A record
in a file may contain several fields.There are certain fields having unique
value.Such a field is primary key.For example employee no is a primary key.
A file can
have fixed length record or variable length record.
fixed
length record: In fixed
length record all record contain the same data item with same amount of space
assigned to each data item.
variable
length record: In
variable length record, file records may contain different lengths.
Apart from
fields,records and files, the data can also be organized into more complex
types of structures.Data can be organsed into different ways.The logical
mathematical model of a particular organization is called a Data Structure.The model should be reflect the
actual relationship of data in real world and it should be simple enough so
that data can be processed whenever required.Some of the data structures are
arrays,linked lists,trees,queue & graph.
An array is a list of finite no of elements.For example an array of names
or an array of marks.
Linked
list is a list
of elements associated with a link to elements of other list.
Tree represents hierarchical relationship between various elements.
Queue is first in first out linear list where deletion can take place
only at one end.
Graph represents relationship between pairs of elements.
Data
Structure Operations:
Following
are operations can be performed on a data structure.
1. Traversing: Traversing means accessing each record(element) only once so
that it can be processed.
2. Searching: Searching means finding the location of recors(element) with
given key value or finding all records that satisfies condition.
3. Inserting: Inserting means adding new record(element) to the structure.
4. Deleting: Deleting means removing the record(element) from the structure.
5. Sorting: Sorting means arranging the records(elements) in some logical
order. For example: arranging names in alphabetical order.
6. Merging: Merging means combining the records in two different files into
a single file.
Algorithms:
Definition:
Algorithm is finite set of instructions that can be followed to
find a solution for given problem. An algorithm must have following
characteristics
1.
Input: An algorithm must accept input if supplied externally.
2.
Output: An algorithm must give at least one output after processing input data.
3.
Definiteness: Each instruction in algorithm must be lucid and unambiguous.
4.
Effectiveness: Each instruction in an algorithm must be practicable. Any person
either expert or novice user must be able to perform the operation with only
pencil and paper.
5. Finiteness: Algorithm must terminate after a finite number of
steps.
An
algorithm is a finite stepbystep list of well defined instructions for
solving a particular problem.
We will
needed to write an algorithm to different data structure operations.
In first
part of algorithm we tell the purpose of algorithm,it list for variable &
input data.
The second
part is list of steps.
The steps in algorithm is executed one after other.
Control
goes transfer to statement n,by using the statement like “Go to step n”.
The exit
& stop statements completes the algorithm.The data may be assigned to
variable by using read statement & it is displayed by write or print
statement.
For
example:
Algorithm
1
:
Purpose of algorithm and input data and variables used.
Step
1
:
……………………………………..
Step
2
:
……………………………………..
:
:
Step
n
:
……………………………………..
Control
Structures:
There are
three types of flow of control(or logic):
1. Sequential flow(Sequential flow)
2. Conditional flow(selection logic)
3. Repetitive flow(Iteration logic)
1.Sequential
flow
Algorithms
consists of modules.Each module is a set of steps.In sequential flow the
module. Are executed one after the other.
Module A
Module B
Module C
:
:
2.Conditional
Flow:
In
conditional flow, one or other module is selected depending on condition. There
are three conditional structure
1. Single
alternative:
This has
the General form
If
condition, then:
[Module A]
[End of if
structure]
Explanation:It
is a selection statement, we have to choice a single alternative like if
statement. If condition is true then it will execute respective module.
1. Double
alternative:
This has
the General form
If
condition, then:
[Module A]
ELSE:
[Module B]
[End of if
structure]
1. Multiple alternative:
This has
the general
form
If condition(1),then:
[Module A_{1}]
ELSE if(condition2) then:
[Module A_{2}]
:
ELSE if(condition M)then:
[Module A_{M}]
ELSE:
[Module B]
[End of if structure]
Explanation:
In Multiple alternative, first check the condition1,if
condition1 is true then it execute first module (moduleA1) otherwise it check
condition2.If condition2 is true then it execute second module(module A2).
this procedure will continue till last condition(Condition M). If all
conditions are failed then it execute else part, i.e. Module B.
The logic of this structure allows only one module to be
executed.

Explanation:
In
repeat for loop first set the initial value, then check the condition. If
condition is true then it will execute respective
Module(body of loop) then increment or decrement the value of variable. Again
it check the condition, code inside the for loop is executed till condition
is getting satisfied.

3. Repititive Flow:
Here certain moule is executed
repetedly unity condition satisfies.
The repeat for loop has the form:
Repeat for k=R to S by T
[Module]
[End of loop]
Here k is index variable, Initial value of K is R and final value is S.T. is
increment.
Repeat While is another repetitive
flow. It has form:
Repeat While Condition:
[Module]
[End of Loop]
Here looping continuous until
condition is false.
Explanation:
In while loop first check the
condition,if condition is true then it execute the body of loop or Module.Again
it check the condition. Again condition is true then it execute Module. This
procedure will continue upto condition becomes false.
If condition becomes false it does
not execute Module
EXERSIZE:
Write an algorithm to find roots
of quadratic equation
Ax_{2}+bx+c=0
Where a≠0 and roots are given by,
X=b±√b^{2}4ac∕2a
Solution:
Algorithm—
This algorithm inputs coefficients
A,B,C of a quadratic equation & find real roots,if any.
Step1: Read:A,B,C
Step2: Set D= b^{2}4ac
Step3: if D>0 then
a) Set X1=(B+√D)/2A and
Set X2=(B√D)/2A
b) Write:’Unique solution’,X
ELSE
Write:’No real roots’
[End of IF structure]
Step 4: EXIT
Arrays:
A linear
array is a list
of a finite number n of homogeneous data elements (i.e., data
elements of the same type) such
that:
(a) The elements of the array are
referenced respectively by an index set consisting of n consecutive
numbers.
(b) The elements of the array are
stored respectively in successive memory locations.
We will analyze this for Linear
Arrays.
The number n of
elements is called the length or size of the array. If not explicitly stated,
we may assume the index set
consists of the integers 1, 2, 3, ….., n.
The general equation to find the
length or the number of data elements of the array is,
Length = UB – LB + 1 (1.4a)
where, UB is the largest index,
called the upper
bound, and LB is
the smallest index,
called the lower bound of the
array. Remember that length=UB when LB=1.
Also, remember that the elements
of an array A may be denoted by the subscript notation,
A1, A2, A3……..An
Let us consider the following example (a),
The following figures (a) and (b) depict the
array DATA.
247

56

429

135

87

156

Figure (a)
247

56

429

135

87

156

Figure (b)
Length = UB – LB + 1
Here UB=5 & LB=0,
Length = 5 –0 + 1 =6
REPRESENTATION OF LINEAR ARRAYS IN
MEMORY
Consider LA be a linear array in
the memory of the computer. As we know that the
memory of the computer is simply a
sequence of addressed location as pictured in
figure as given below.
1000
1001
1002
1003
1004
1005
.
.
.
.
.
.
.
.
.
.
Figure:
Computer Memory
TRAVERSING LINEAR ARRAYS
Consider let A be a collection of
data elements stored in the memory of the computer.
Suppose we want to either print
the contents of each element of A or to count the number of elements of A with
a given property. This can be accomplished by traversing A, that is, by accessing and processing (frequently called visiting) each element of A exactly once.
The following algorithm is used to traversing a linear array
LA.
As we know already, here, LA is a
linear array with lower bound LB and upper bound
UB. This algorithm traverses LA
applying an operation PROCESS to each element of
LA.
1. [Initialize counter] Set K:=
LB.
2. Repeat Steps 3 and 4 while K≤UB
3. [Visit element] Apply PROCESS
to LA[K]
4. [Increase counter] Set K:= K +
1
[End of Step 2 loop]
5. Exit.
INSERTING AND DELETING
Let A be a collection of data
elements in the memory of the computer. “Inserting” refers to the operation of
adding another element to the collection A, and “deleting” refers to the
operation of removing one of the elements from A. Let we discuss the inserting
and deleting an element when A is a linear array.
Inserting an element at the “end”
of a linear array can be easily done provided the
memory space allocated for the
array is large enough to accommodate the additional
element. On the other hand,
suppose we need to insert an element in the middle of the array. Then, on the
average, half of the elements must be moved downward to new locations to
accommodate the new element and keep the order of the other elements.
Similarly, deleing an element at
the “end” of an array presents no difficulties, but deleting an element somewhere
in the middle of the array would require that each subsequent element be moved
one location upward in order to “fill up” the array.
Consider the other example
Suppose NAME is an 8element
linear array, and suppose five names are in the array, as in Figure (a). Observe that the names are listed
alphabetically, and suppose we want to keep the array names alphabetical at all
times. If, Ford is adding to the array, then,
Johnson, Smith and Wagoner must each be move downward one location, as given in Figure (b). Next if we add Taylor to this array; then Wagner must be move, as in Figure (c). Last,
when we remove Davis from the array, then, the five names Ford, Johnson,
Smith, Taylor and Wagner must each be move upward one location, as in Figure (d). We may observe, clearly that such movement
of data would be very expensive if thousands of names are in the array
TRAVERSING LINEAR ARRAYS
Consider let A be a collection of
data elements stored in the memory of the computer.
Suppose we want to either print
the contents of each element of A or to count the number of elements of A with
a given property. This can be accomplished by traversing A, that is, by accessing and processing (frequently called visiting) each element of A exactly once.
The following algorithm is used to traversing a linear array
LA.
As we know already, here, LA is a
linear array with lower bound LB and upper bound
UB. This algorithm traverses LA
applying an operation PROCESS to each element of
LA.
1. [Initialize counter] Set K:=
LB.
2. Repeat Steps 3 and 4 while K≤UB
3. [Visit element] Apply PROCESS
to LA[K]
4. [Increase counter] Set K:= K +
1
[End of Step 2 loop]
5. Exit.
INSERTING AND DELETING
Let A be a collection of data
elements in the memory of the computer. “Inserting” refers to the operation of
adding another element to the collection A, and “deleting” refers to the
operation of removing one of the elements from A. Let we discuss the inserting
and deleting an element when A is a linear array.
Inserting an element at the “end”
of a linear array can be easily done provided the
memory space allocated for the
array is large enough to accommodate the additional
element. On the other hand,
suppose we need to insert an element in the middle of the array. Then, on the
average, half of the elements must be moved downward to new locations to
accommodate the new element and keep the order of the other elements.
Similarly, deleing an element at
the “end” of an array presents no difficulties, but deleting an element
somewhere in the middle of the array would require that each subsequent element
be moved one location upward in order to “fill up” the array.
Consider the other example
Suppose NAME is an 8element
linear array, and suppose five names are in the array, as in Figure (a). Observe that the names are listed
alphabetically, and suppose we want to keep the array names alphabetical at all
times. If, Ford is adding to the array, then,
Johnson, Smith and Wagoner must each be move downward one location, as given in Figure (b). Next if we add Taylor to this array; then Wagner must be move, as in Figure (c). Last,
when we remove Davis from the array, then, the five names Ford, Johnson,
Smith, Taylor and Wagner must each be move upward one location, as in Figure (d). We may observe, clearly that such movement
of data would be very expensive if thousands of names are in the array
ALGORITHM FOR INSERTING:
The following algorithm inserts a data element ITEM into the
Kth position in a
linear
array LA with N elements i.e.
INSERT(LA,N,K,ITEM).
Here LA is a linear array with N
elements and K is a positive integer such that K<N.
This
algorithm inserts an element ITEM into the Kth position in LA.
ALGORITHM FOR DELETING:
The following algorithm deletes the Kth element from a linear array LA and assigns it to
a variable ITEM i.e.
DELETE{LA.N,K,ITEM).
Here LA is a linear array with N
elements and K is a positive integer such that K<N.
This algorithm deletes the Kth
element from LA.
Sorting:
Sorting means rearranging elements
of array in increasing order,i.e.
A[0]<A[1]
<A[2]………………. <A[n]
Where A is array name.
For example,suppose A originally
is the list
8,4,19,2,7,13,5,16
After sorting A is the list
2,4,5,7,8,13,16,19
In sorting we may rearrange the data
in decreasing also.There are many sorting techniques,here we discuss the simple
sorting technique,Bubble sort.
Suppose
the list of numbers, A[0]<A[1] <A[2]………………. <A[n]
In memory.
ALGORITHM FOR BUBBLE SORT:
Step1:
Compare A[1] and A[2]
and arrange them in desired order,so that A[1]<A[2].Then compare A[2] A[2]
and A[3] and arrange them so that A[2]<A[3].
Continue this process until we
compareA[n1]<A[N].
Step 1 involves n1
comparisons.During this step,the largest element is coming like a bubble to the
nth position.When step 1 is completed,A[N} will be the largest element.
Step 2:
Repeat step 1 with one less comparision. Step 2 involves N2 comparision,when
step 2 is completed we get second element A[N2}.
Step 3:
Repeat step 1 with one less comparision. Step 3 involves N3 comparision,
Step N1:
Compare A[1] and A[2] and arrange them so that A[1]<A[2].
After N1 steps,the list will be
sorted in increasing order.Each step is called as ‘pass’.So that bubble sort
has n1 passes.
Algorithm: (BUBBLE SORT)
BUBBLE (DATA, N)
Here DATA is an array with N elements. This algorithm sorts the
elements in DATA.
1. Repeat step 2 and 3 for K=1 to N1
2. Set PTR :=1 [Initializes pass pointer PTR]
3. Repeat while PTR <= NK [Executes pass]
a. If DATA [PTR]> DATA [PTR+1], then:
Interchange DATA [PTR] and
DATA [PTR+1].
[End of if structure].
b. Set PTR: = PTR+1.
[End of inner loop].
4. EXIT.
Searching
Many
times we need to find a record with the help of key. Key is the unique value
associated with each record which distinguishes records from each other.
Searching is operation that finds the given key value in the list of elements.
Searching algorithm accepts two arguments the key and list in which key is to
be found. There are two standard algorithm for searching – Linear Search and
Binary search. Linear
Searching This
is the simplest method for searching a element into the list of elements. We
start from the beginning of the list and search the element by examining each
consequetive element in the list until the element found in the list or the
list is finished. Algorithm
1. Read N elements into an
array A.
2. Read the element to be
searched into KEY.
3. Repeat step 4 for I=0
to N1 by 1.
4. IF A[I] = KEY THEN
PRINT “Element found”.
5.
IF element is not in the list PRINT “Element not found”.
Algorithm: (Linear
Search) LINEAR (DATA, N, ITEM, LOC)
Here DATA is linear array with N elements, and ITEM is a given
item of information. This algorithm finds the location LOC of ITEM in
DATA, or sets LOC: = 0 if search is unsuccessful.
1. [Insert ITEM at the end of DATA] Set DATA [N+1]:= ITEM
2. [Initialize counter] Set LOC: =1.
3. [Search for ITEM]
Repeat while DATA [LOC]! =
ITEM
Set LOC: = LOC+1.
[End of loop].
4. [Successful?] If LOC= N+1, then Set LOC: =0.
5. EXIT
Binary Search:
Binary Search:
Suppose DATA is an array which is stored in increasing numerical order or
alphabetically. Then there is an extremely efficient searching algorithm called
binary search, which can be used to find the location LOC of a given ITEM of
information in DATA.
The Binary Search algorithm applied to our array DATA works as
follows. During each stage of our algorithm, our search of ITEM is reduced to a
segment of element of DATA:
DATA [BEG], DATA [BEG+1], DATA [BEG+2], …… DATA [END]
Note that the variables BEG and END denote, respectively, the
beginning and end location of the segment under consideration. The algorithm
compares ITEM with the middle element DATA [MID] of the segment, where MID is
obtained by
MID = INT ((BEG + END)/2)
If
DATA [MID] =ITEM, then the search is successful and we set LOC:= MID. Otherwise
a new segment of DATA is obtained as follows:
a) If ITEM < DATA[MID], then ITEM can appear only in the left
half of the segment:
DATA
[BEG], DATA [BEG+1], …. DATA [MID1]
So
we reset END: = MID1 and begin search again.
b) If ITEM > DATA[MID], then ITEM can appear only in the right
half of the segment:
DATA
[MID+1], DATA [MID+2], … DATA[END]
So
we reset BEG: = MID +1 and begin search again.
Algorithm: (Binary Search)
BINARY (DATA, LB, UB, ITEM, LOC)
Here DATA is stored array with lower bound LU and upper bound
UB, and ITEM is given item of
information. The variables BEG, END and MID denote, respectively, the beginning
end and middle location of the segment of an
element of DATA. This algorithm finds the location LOC of ITEM in DATA
or set LOC= NULL.
1. [Initialize segment variable]
Set BEG: = LB, END: = UB
and MID: = INT ((BEG+END)/2).
2. Repeat Step 3 and 4 while BEG<= END and DATA [MID]!= ITEM.
3. If ITEM < DATA[MID], then
Set END: = MID1
ELSE:
Set BEG: = MID+1.
[End of if structure]
4. Set MID: =INT((BIG+END)/2)
[End of Step 2 loop]
5. If DATA[MID]= ITEM then
Set LOC: = MID
ELSE:
Set LOC: = NULL.
[End of if structure]
6. EXIT.
Pointer Arrays:
A variable is called pointer if it
points to an element in list.The pointer variable contains the address of an
element in the list.
An array is called pointer array
if each element of array is a pointer.The use of pointer array can be stored in
memory.The most efficient method is to form two arrays.One is member consisting
of list of all members one after the other and another pointer array group
containing the starting locations of different groups.
It is shown in fig.
Records:
Record is a collection of fields.A
record may contain non homogeneous data,i.e.data item in a record may have
different data types.In records,the natural ordering of element is not
possible.
The element in records can be described by level numbers.For example,A hospital
keeps a record of new born baby.It contains following data
items:Name,Sex,Birthday,Father,Mother.
Birthday is a group item
consisting month,day,year,
Father & Mother are also group
item with subitem name & age.
The structure of this item is
shown below.
1.New born
2. Name
2. Sex
2.
Birthday
3. Month
3. Day
3. Year
2. Father
3. Name
3. Age
2. Mother
3. Name
3. Age
The number to left of each
variable is called a level number.
Each group item is followed by its
subitem.The level of subitem is 1 more than the level of group item.
To indicate number of records in a file we may write
1 Newborn(20)
It indicates a file of 20 records.
For example:
In above record,if we want to
refer to the age of the father then it can be done by writing
Newborn.father.Age.
If there
are 20 records and we want to refer to sex of sixth newborn then it can be done
by writing Newborn.sex[6].
Linked List:
BASIC TERMINLOGY
A linked
list, or oneway list, is a linear collection of data elements,
called nodes, where
the linear order is given by means
of pointers. That is, each node is divided into two parts: the first part
contains the
information of the element, and the second part, called the link field or next pointer field, contains the address of the next
node in the list.
Figure is a
schematic diagram of a linked list with 6 nodes, Each node is pictured with two
parts. 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. The pointer of the last node contains special value, called
the null pointer, which is any invalid address.
REPRESENTATION OF LINKED LISTS IN
MEMORY
Let LIST be a linked list. Then
LIST will be maintained in memory as follows. First of all, LIST requires two
linear arrayswe will call them here INFO and LINK  such that INFO[K] and
LINK[K] contain the information part and the next pointer field of a node of
LIST respectively. START contains the location of the beginning of the list,
and a next pointer sentineldenoted by NULLwhich indicates the end of the
list.
The following examples of linked
lists indicate that more than one list may be maintained in the same linear
arrays INFO and LINK. However, each list must have its own pointer variable
giving the location of its first node.
START
INFO
LINK
START = 9, so INFO[9] = N is the
first character.
LINK[9] = 3, so INFO[3] = O is the
second character.
LINK[3] = 6, so 1NFO[6] = (blank)
is the third character.
LINK[6] = 11, so INFO[11] = E is
the fourth character.
LINK[11] = 7, so INFO[7] = X is
the fifth character.
LINK[7] = 10, so INFO[10] = I is
the sixth character.
LINK[10] = 4, so INFO[4] = T is
the seventh character.
LINK[4] = 0, so the NULL value, so
the list has ended.
Tree
A tree is
a connected acyclic graph in which one vertex is singled out as the root &
several other vertices connected to it by an edge inherit a parent child
relationship. Again each node is further connected to their child nodes making
set of trees
Binary Tree
In
computer science a most important type of tree structure is a binary tree. In
this type of tree any node will have atmost two branches i.e. degree of each
node will be atmost two. We distinguish the two branches of tree as left
subtree and right subtree.
A binary tree T is defined as a
finite set of elements, called nodes, such that
a) T is empty (called the null tree or empty tree) or
b) T contains a distinguished node R,called root of T and remaining
nodes of T form ordered pair of disjoint binary trees T1 and T2.
If T contains root R,then two
trees T1 & T2 are left & right subtrees of R.If T1 is nonempty then its
root is called as left successor of R & if T2 is nonempty then its root is
called as right successor or R.
T contains 11 nodes (A to L).Root
of T is A at the top of fig.B is left successor & C is right successor of
node A.Left subtree of node A consist of nodes B,D,E & F. Right subtree of
node A consist of nodes C,G,H,J,K & L.
Any node in binary tree has 0,1 or
2 successors. The node with no successors are called terminal nodes.
The two binary trees are said to
be similar if they have same structure.
The algebraic expression
E=(ab)/((c*d)+e) can be represented by binary tree as shown in fig.
Fig.
expression E=(ab)/((c*d)+e)
Suppose N is node in T with left
successor S1 & right successor S2,Then N is called parent of S1 & S2.S1
is left child of N & S2 is right child of N.The line drawn from node N to a
successor is called an edge & sequence of consecutive edge is called a
path.
A terminal node is leaf & path
ending in a leaf is called a branch. The defth(hight) of tree T is the maximum
no of nodes in a branch of T.
The tree T is said to be complete
if all its levels,except the last.have maximum mo of possible nodes.
A binary tree T is said to be a 2
tree or an extended binary tree if each node N has either 0 or 2 children.In
such a case,the nodes with 2 children are called internal nodes & the nodes
with 0 children are called external nodes,It is shown in fig.
Fig.Extended
2tree
The depth(or hight) of a tree T is
the maximum no of nodes in a branch of T.This is one more than the largest
level no of T,
For example:Following tree has
depth 5.
The maximum no of nodes symmetric
binary with depth 5 are 31.
Representation of Binary tree in
memory
Let T be a binary tree.T can be
represented in memory either by link reprentation or by using array alled
sequential representation.The requirement in any representation is that one
should have direct access to root R given any node N of T.
The linked representation uses three parallel arrays,INFO,LEFT & RIGHT
& a pointer variable ROOT.Each node N of Y will correspond to a location K
such that:
1) INFO[K] contains the data at node N.
2) LEFT[K] contains the location of left child of node N.
3) RIGHT[K] contains the location of right child of node N.
ROOT will contain location of root
R of T.
A sample representation is shown
in fig.
Another method is sequential
representation.Here a linear array is used.The root R is stored in TREE[1].If a
node n occupies TREE[K],then its left child in TREE[2*K]& right child TREE
[2*K+1].An example shown below.
Stack And Queue:
STACK:
Stacks and Queues are two data
structures that allow insertions and deletions operations only at the beginning
or the end of the list, not in the middle. A stack is a linear structure in
which items may be added or removed only at one end. Figure pictures
three everyday examples of such a structure: a stack of dishes, a stack of
pennies and a stack of folded towels.
Stacks are also called lastin
firstout (LIFO) lists. Other names used for stacks are "piles" and
"pushdown lists. Stack has many important applications in computer
science.The notion of recursion is fundamental in computer science. One way of simulating
recursion is by means of stack structure. Let we learn the operations which are
performed by the Stacks.
Figure
Of STACK
QUEUE
A queue is a linear structure in
which element may be inserted at one end called the rear, and the deleted at the other end called the front. Figure pictures a queue of people waiting at a bus stop. Queues are
also called firstin firstout (FIFO) lists. An important example of a queue in
computer science occurs in a timesharing system, in which programs with the
same priority form a queue while waiting to be executed. Similar to stack
operations, operations that are define a queue.
Figure of
Queue
**********ALL
THE BEST**********
No comments:
Post a Comment