Trees

INTRODUCTION OF TREES:
         Trees are one of the most important data structures in computer science. Trees are very flexible, versatile and powerful data structures that can be used to represent data items possessing hierarchical relationship between the grandfather and his descendants and their descendants and so on.

        A tree is a non-linear data structure in which items are arranged in a sorted sequence. It is used to represent hierarchical relationship existing among several data items.

DEFINITION: 
Tree is a finite set of one or more data items(nodes)” such that
1.  There is a special data item called the root of the tree

2. The remaining data items are partitioned into number of mutually exclusively (i.e.., disjoint) subsets, each of which is itself a tree, and they are called “Subtrees”.

TREE TERMINOLOGY:

        There are number of terms associated with the trees which are    listed below-     

1.  Root

2.  Node

3.  Degree of a node

4.  Degree of a tree

5.  Terminal node

6.  Non-terminal node

7.  Siblings

8.  Level

9.  Edge

10.Path

11.Depth

12.Height

13.Forest

(1)  ROOT:-  It is specially designed data item in a tree. It is the first in the hierarchial arrangement of data items. In the above tree,
A is the root item.                                                                                    

(2) Node:- Each data item in a tree is called a node. It is the basic structure in a tree, it specifies the data information and links (branches) to other data items. There are 8 nodes in the above tree.

(3) Degree of a node:- In the above tree-

                        The degree of node A is 2

                        The degree of node C is 1

                        The degree of node B is 3

                        The degree of node H is 0

                      

(4) Degree of a tree:- It is the maximum degree of nodes in a given tree. In the above tree the node A has degree 3 and another node C is also having its degree 1. In all this, value is the maximum. So, the degree of the above tree is 3.

(5) Terminal node (or) leaf node (s);- A node with degree zero is called a terminal node (or) a leaf. In the above tree, there are 4 terminal nodes, they are D,F,G,H.

(6) Non-terminal node (or) internal node (s):-Any node (except the root node) whose degree is not zero is called non-terminal node. Non-terminal nodes are the intermediate nodes in traversing the given tree from its root node to the terminal nodes (leaves). There are 3 non-terminal nodes B, E,C.

(7) Siblings;- The children nodes of a given parent node are called “siblings”. They are also called brothers. In the above tree,
Ø B and C are siblings of parent node A.
Ø D,E,F are siblings of parent node B.

(8) LEVEL:- The entire tree structure is leveled in such a way that the root node is always at level 0. Then, its immediate children are at level 1 and their immediate children are at level 2 and so on upto the terminal nodes. In general, if a node is at level n, then its children will be at level n+1, in the 4 levels.

(9) EDGE:- It is a connecting line of two nodes. i.e.., the line drawn from one node to another node is called an edge.

(10) PATH:- It is a sequence of consecutive edges from the source node to the destination node. In the above tree, the path between A and H is given by the node pairs.

                        (A, B), (B, E) and (E,H)

(11) DEPTH:- It is the maximum level of any node in a given tree towards the root node is called  Depth 
In the above tree, the root node B has the Depth of 1 
the root node E has the Depth of 2  

(12) HEIGHT:-It is the maximum level of any node in a given tree towards the leaf node is called Height 
In the above tree, the root node B has the Height of 2 
the root node C has the Height of 1  

(13) FOREST:- It is a set of disjoint trees. In a given tree, if you remove its root node then it becomes a forest. In the above tree, there is forest with three trees.

BINARY TREES:-

        A binary tree is a finite set of data items which is either empty or consists of a single item called the root and two disjoint binary trees called the left subtree and right subtree.

A binary tree is a very important and the most commonly used non-linear data structure. In a binary tree the maximum degree of any node is atmost two. i.e.., there may be a zero degree node (usually an empty tree) or a one degree node and two degree node. Figure shows a binary tree consisting of 6 elements.

        In the above binary tree, A is the root of the tree. The left subtree consists of the tree with root B, and the right subtree consists of the tree with root C. Further B has its left subtree with root D 

        Similarly, C has its left subtree with root E and its right subtree with root F. In the next level, D has an empty left subtree. F has neither its left subtree nor right subtree 

FULL/STRICTLY BINARY TREES:-  If every non-terminal node in a binary tree consists of non-empty left subtree, then such a tree is called strictly binary tree.

NOTE: EVERY NODE MUST HAVE 2 CHILDREN EXCEPT THE LEAF NODE

COMPLETE/ PERFECT BINARY TREE:-  A binary tree with ‘n’ nodes and depth ‘d’ is a strictly binary tree all of  whose terminal nodes are at level ‘d’. In a complex binary tree, there is exactly one node at level 0, two nodes at level 1, and four nodes at level 2 and so on.

        If there are m nodes at level 1then a binary tree contains at most 2m nodes at level 1+1. A binary tree has exactly one node at the root level and has at most 2¹ nodes at level 1. Taking into consideration of this property, we can show further that a complete binary tree of depth d contains exactly 2¹ nodes at each level. The value 1 ranges from 0 to d. Figure shows a complete binary tree of depth 4.

NOTE: EVERY NODE MUST HAVE 2 CHILDREN IN ALL THE LEVELS AND AT EACH LEVEL THERE SHOULD BE 2 POWER LEVEL NODE ( I.E LEVEL 2 SHOULD HAVE 4 NODES )

INCOMPLETE/ALMOST BINARY TREE: every node must have two children in all the levels except in the last level  , fill the nodes from left to right 

TRAVERSING  IN  A  BINARY TREE (OR)

BINARY TREE APPLICATIONS:-

In tree creation we take 3 parameters node, left child and right child, so traversing of binary tree means traversing of node, left subtree and right subtree.

If root is denoted as N, left subtree as L and right subtree as R, then there will be six combinations of traversals.
Ø NRL
Ø NLR
Ø LNR
Ø LRN
Ø RNL
Ø RLN

But only three standard,   NLR (node-left-right) preorder

                                       LNR (left-node-right) in order

                                       LRN (left-right-node) post order

Preorder (NLR traversal)-

1.  Visit the root.

2.  Traverse the left subtree of root in preorder.

3.  Traverse the right subtree of root in preorder.

Inorder (LNR traversal)-

1.  Traverse the left subtree of root in inorder.

2.  Visit the root.

3.  Traverse the right subtree of root in inorder.

Postorder (LRN traversal)-

1.  Traversal the left subtree of root in postorder.

2.  Traverse the right subtree of root in postorder.

3.  Visit the root.

OPERATIONS  ON  BINARY TREES:-

        The basic operations to be performed on a binary are listed as follows-

1.  CREATE- It creates an empty binary tree.

2.  MAKE BINARY TREE- It creates a new binary tree having a single node with data field set to some value.

3.  EMPTY BINARY TREE- It returns true if the binary tree is empty otherwise it returns false.

4.  LEFT CHILD- It returns a pointer to the left child of the node. If the node has no left child it returns the null pointer.

5.  RIGHT CHILD- It returns a pointer to the right child of the node. If the node has no right child it returns the null pointer.

6.  FATHER- It returns a pointer to the father of the node. Otherwise returns the null pointer.

7.  BROTHER- It returns a pointer to the brother of the node. Otherwise returns the null pointer.

8.  DATA- It returns the contents of the node.

Apart from these primitive operations, other operations can be applied to the binary tree are –

Ø Tree traversal

Ø Insertion of nodes

Ø Deletion of nodes

Ø Searching for the node

Ø Copying the binary tree.

BINARY TREE REPRESENTATIONS-

                        There are two ways by which we can represent a binary tree.
(1)Linked representation of a binary  tree
(2)Array representation of a binary tree

(1)LINKED REPRESENTATION OF A BINARY TREE- The basic component to be represented in a binary tree is a node. The node consists of three fields such as

ü Data

ü Left child

ü Right child

The data field holds the value to be given. The left child is a link field which contains the address of its left node and the right child contains the address of the right node. Figure shows a structure of a node.

(2)Array representation of a binary tree

        An array can be used to store the nodes of a binary tree. The nodes stored in an array are accessible sequentially. In C, arrays start with index 0 to (maxsize-1). The maximum number of nodes is specified by MAXSIZE.

        The root node is always at index 0. Then in successive memory locations the left child and right child are stored. Consider a binary tree with only three nodes as shown. Let BT denote a binary tree.