By: Ms. Shailja Chaurasiya(Asst. Prof.- Dept.of CSE)
DATA STRUCTURE
UNIT-IV NOTES
By: Ms. Shailja Chaurasiya
Assistant Professor
(Deptt. Of CSE @BBD University)
,UNIT- IV TREES
UNIT IV
Trees
Introduction Terminology
Representation of trees,
Binary trees abstract data type
Properties of binary trees
Binary tree representation
Binary tree traversals: In order, preorder, post order
Binary search trees Definition
Operations:searching BST, insert into BST, delete from a BST, Height of a BST.
Trees: Non-Linear data structure
A data structure is said to be linear if its elements form a sequence or a linear list. Previous
linear data structures that we have studied like an array, stacks, queues and linked lists organize
data in linear order. A data structure is said to be non linear if its elements form a hierarchical
classification where, data items appear at various levels.
Trees and Graphs are widely used non-linear data structures. Tree and graph structures represent
hierarchical relationship between individual data elements. Graphs are nothing but trees with
certain restrictions removed.
Trees represent a special case of more general structures known as graphs. In a graph, there is no
restrictions on the number of links that can enter or leave a node, and cycles may be present in the
graph. The figure 5.1.1 shows a tree and a non-tree.
Tree is a popular data structure used in wide range of applications. A tree data structure can be
defined as follows...
Tree is a non-linear data structure which organizes data in hierarchical structure and this is a
recursive definition.
A tree data structure can also be defined as follows...
A tree is a finite set of one or more nodes such that:
1
, UNIT- IV TREES
There is a specially designated node called the root. The remaining nodes are partitioned into n>=0
disjoint sets T1, ..., Tn, where each of these sets is a tree. We call T1, ..., Tn are the subtrees of the
root.
A tree is hierarchical collection of nodes. One of the nodes, known as the root, is at the top of the
hierarchy. Each node can have at most one link coming into it. The node where the link originates is
called the parent node. The root node has no parent. The links leaving a node (any number of links
are allowed) point to child nodes. Trees are recursive structures. Each child node is itself the root of
a subtree. At the bottom of the tree are leaf nodes, which have no children.
Advantages of trees
Trees are so useful and frequently used, because they have some very serious advantages:
Trees reflect structural relationships in the data
Trees are used to represent hierarchies
Trees provide an efficient insertion and searching
Trees are very flexible data, allowing to move sub trees around with minimum effort
Introduction Terminology
In a Tree, Every individual element is called as Node. Node in a tree data structure, stores the actual
data of that particular element and link to next element in hierarchical structure. Example
2
DATA STRUCTURE
UNIT-IV NOTES
By: Ms. Shailja Chaurasiya
Assistant Professor
(Deptt. Of CSE @BBD University)
,UNIT- IV TREES
UNIT IV
Trees
Introduction Terminology
Representation of trees,
Binary trees abstract data type
Properties of binary trees
Binary tree representation
Binary tree traversals: In order, preorder, post order
Binary search trees Definition
Operations:searching BST, insert into BST, delete from a BST, Height of a BST.
Trees: Non-Linear data structure
A data structure is said to be linear if its elements form a sequence or a linear list. Previous
linear data structures that we have studied like an array, stacks, queues and linked lists organize
data in linear order. A data structure is said to be non linear if its elements form a hierarchical
classification where, data items appear at various levels.
Trees and Graphs are widely used non-linear data structures. Tree and graph structures represent
hierarchical relationship between individual data elements. Graphs are nothing but trees with
certain restrictions removed.
Trees represent a special case of more general structures known as graphs. In a graph, there is no
restrictions on the number of links that can enter or leave a node, and cycles may be present in the
graph. The figure 5.1.1 shows a tree and a non-tree.
Tree is a popular data structure used in wide range of applications. A tree data structure can be
defined as follows...
Tree is a non-linear data structure which organizes data in hierarchical structure and this is a
recursive definition.
A tree data structure can also be defined as follows...
A tree is a finite set of one or more nodes such that:
1
, UNIT- IV TREES
There is a specially designated node called the root. The remaining nodes are partitioned into n>=0
disjoint sets T1, ..., Tn, where each of these sets is a tree. We call T1, ..., Tn are the subtrees of the
root.
A tree is hierarchical collection of nodes. One of the nodes, known as the root, is at the top of the
hierarchy. Each node can have at most one link coming into it. The node where the link originates is
called the parent node. The root node has no parent. The links leaving a node (any number of links
are allowed) point to child nodes. Trees are recursive structures. Each child node is itself the root of
a subtree. At the bottom of the tree are leaf nodes, which have no children.
Advantages of trees
Trees are so useful and frequently used, because they have some very serious advantages:
Trees reflect structural relationships in the data
Trees are used to represent hierarchies
Trees provide an efficient insertion and searching
Trees are very flexible data, allowing to move sub trees around with minimum effort
Introduction Terminology
In a Tree, Every individual element is called as Node. Node in a tree data structure, stores the actual
data of that particular element and link to next element in hierarchical structure. Example
2
