Unit-IV
TREES & GRAPHS
, Trees
• It is a non-linear data structure.
• This structure is used to represent data
containing a hierarchical relationship between
elements.
, Binary Tree
• A binary tree T is defined as a finite set of elements called nodes such that:
– T is empty (called null tree of empty tree)
– T contains a distinguished node R, called root of T, and the remaining nodes of T form
an ordered pair of disjoint binary trees T1 and T2.
• If T contains a root R,
– T1 is called the left successor of R.
– T2 is called the right successor of R.
• The nodes with no successors are called terminal nodes.
• Binary trees T and T’ are said to be similar if they have the same structure (or
same shape).
• The trees are said to be copies if they are similar and having the same contents
at the corresponding nodes.
, Example
TREES & GRAPHS
, Trees
• It is a non-linear data structure.
• This structure is used to represent data
containing a hierarchical relationship between
elements.
, Binary Tree
• A binary tree T is defined as a finite set of elements called nodes such that:
– T is empty (called null tree of empty tree)
– T contains a distinguished node R, called root of T, and the remaining nodes of T form
an ordered pair of disjoint binary trees T1 and T2.
• If T contains a root R,
– T1 is called the left successor of R.
– T2 is called the right successor of R.
• The nodes with no successors are called terminal nodes.
• Binary trees T and T’ are said to be similar if they have the same structure (or
same shape).
• The trees are said to be copies if they are similar and having the same contents
at the corresponding nodes.
, Example
