Let us get introduced with some of the definitions or terms which are normally used.
Basic Terminologies
Let us
get introduced with some of the definitions or terms which are normally used.
1. Root
Root is
a unique node in the tree to which further subtrees are attached. For above
given tree, node 10 is a root node.
2. Parent node
The node
having further sub-branches is called parent node. In Fig. 4.2.2 the 20 is
parent node of 40, 50 and 60.
3. Child nodes
The
child nodes in above given tree are marked as shown below
4. Leaves
These
are the terminal nodes of the tree.
For
example -
5. Degree of the node
The
total number of subtrees attached to that node is called the degree of a node.
For
example.
6. Degree of tree
The
maximum degree in the tree is degree of tree.
7. Level of the tree
The root
node is always considered at level zero.
The
adjacent nodes to root are supposed to be at level 1 and so on.
8. Height of the tree
The
maximum level is the height of the tree. In Fig. 4.2.7 the height of tree is 3.
Sometimes height of the tree is also called depth of tree.
9. Predecessor
While
displaying the tree, if some particular node occurs previous to some other node
then that node is called predecessor of the other node.
For example: While displaying the tree
in Fig. 4.2.7 if we read node 20 first and then if we read node 40, then 20 is
a predecessor of 40.
10. Successor
Successor is a node which occurs next
to some node.
For example: While displaying tree in
Fig. 4.2.7 if we read node 60 after-reading node 20 then 60 is called successor
of 20.
11. Internal and external nodes
Leaf
node means a node having no child node. As leaf nodes are not having further
links, we call leaf nodes External nodes and non leaf nodes are called internal
nodes.
12. Sibling
The
nodes with common parent are called siblings or brothers.
For
example
In this
chapter we will deal with special type of trees called binary trees. Let us
understand it.
Data Structure: Unit III: Trees : Tag: : ADT Data Structure - Basic Terminologies in Trees
Data Structure
CS3301 3rd Semester CSE Dept | 2021 Regulation | 3rd Semester CSE Dept 2021 Regulation