The Binary Tree complete discussion

 

The Binary Tree

Types of Binary Trees:

Binary Search Trees

Threaded Binary Tree

Expression Trees

Decision Tree

Fibanocci Tree

Selection Trees

Balanced Binary Trees

AVL Trees

M-Way Search Trees

2-3 Trees

2-3-4 Trees

Red-Black Tree

B-Tree

Splay Trees

Digital Search Trees

 

First, we should know that a tree is a non-linear data structure. Trees are very flexible and versatile, that can be used to represent data items possessing hierarchical relationships between the grandfather and his children and grandchildren as so on.

In other words: “A binary tree is a non-linear data structure with a maximum of two children for each parent node.”

A tree is an ideal data structure for representing hierarchical data. A tree can be defined (theoretically) as a finite set of one or more data items (or nodes) such that :

1. There is a special node called the root of the tree.

2. Removing nodes (or data items) are partitioned into a number of mutually   
     exclusive (i.e., disjoined) subsets each of which is itself a tree, are called
      a subtree.

BASIC TERMINOLOGIES

Root is a specially designed node (or data items) in a tree. It is the first node in the hierarchical arrangement of the data items. ‘A’ is a root node in the Fig.

Each data item in a tree is called a node. It specifies the data information and links (branches or edges) to other data items.

This section discusses two ways of representing binary tree T in memory:

·        Sequential representation using arrays

·        Linked list representation

The degree of a node is the number of subtrees of a node in a given tree. In Fig.

The degree of node A is 3

The degree of node B is 2 "The degree of node C is 2

The degree of node D is 3

The degree of a tree is the maximum degree of node in a given tree. In the above tree, degree of a node J is 4. All the other nodes have less or equal degree. So the degree of the above tree is 4. A node with degree zero is called a terminal node or a leaf. For example, in the above tree Fig M, N, I, O, P,Q, R,S are leaf nodes. Any node whose degree is not zero is called non-terminal node. They are intermediate nodes in traversing the given tree from its root node to the terminal nodes.

The tree is structured in different levels. The entire tree is leveled so that the root node is always of level O. Then, its immediate children are at level 1 and their immediate children are at level 2, and so on up to the terminal nodes. That is, if a node is at level n, then its children will be at level n + 1.

The Depth of a tree is the maximum level of any node in a given tree. That is a number of level one can descend the tree from its root node to the terminal nodes (leaves).
The term height is also used to denote the depth.

 

 

• Binary tree: A rooted tree where every node has at most two children. 
• Full binary tree: A binary tree where every node has either zero or two children. 
• Complete binary tree: A binary tree where all levels are filled with nodes, except possibly for the last level. 
• Perfect binary tree: A binary tree where all internal nodes have two children and all leaf nodes are at the same level. 
• Balanced binary tree: A binary tree where the height of the left and right subtrees of each node varies by at most one. 
• Degenerate binary tree: A binary tree where every internal node has only a single child. 
• Leaf node: A terminal node with no further branches or nodes emerging from it. 
• Internal node: A node that has at least one child. 
• Degree: The total number of children of a node. 
• Level: The root node is at Level 0, the children of the root node are at Level 1, and so on. 
• Left child: The node is present to the left of the parent node. 

 ARRAY REPRESENTATION

 We know that an array can be used to store the nodes as a binary tree. The nodes stored in an array of memory locations can be accessed sequentially.

Suppose a binary tree T of depth d. Then at most 2d – 1 nodes can be there in T.(i.e., SIZE = 2d–1)

So the array of size “SIZE” to represent the binary tree. Consider a binary tree in Fig. of depth 3. Then

SIZE = 2³ – 1 = 7. Then the array A[7] is declared to hold the nodes.

 

The array representation of the binary tree is shown in Fig. 8.9. To perform any operation often we have to identify the father, the left child and right child of an arbitrary node.

 1. The father of a node having index n can be obtained by (n – 1)/2. For example to find the father

            of D, where array index n = 3. Then the father nodes index can be obtained

            = (n – 1)/2

            = 3–1/2

            = 2/2

            = 1

            i.e.,     A[1] is the father D, which is B.

2. The left child of a node having index n can be obtained by (2n+1). For example to find the left

            child of C, where array index n = 2. Then it can be obtained by

            = (2n +1)

            = 2*2+1

            = 4 + 1

            = 5

            i.e.,     A[5] is the left child of C, which is NULL. So no left child for C.

 3. The right child of a node having array index n can be obtained by the formula (2n  + 2). For example to find the right child of B, where the array index n = 1. Then

            = (2n + 2)

            = 2*1+2

            = 4

            i.e.,     A[4] is the right child of B, which is E.

4. If the left child is at array index n, then its right brother is at (n + 1). Similarly,
    if the right child is at index n, then its left brother is at (n – 1).

  The array representation is more ideal for the complete binary tree.
  The Fig. is not a complete binary tree. Since there is no left child for node C, i.e.,
  A[5] is vacant. Even though memory is allocated for A[5] it is not used,
  so wasted unnecessarily.

The Trees can be divided in different classes that is below:

 

LINKED LIST REPRESENTATION

The most popular and practical way of representing a binary tree is using linked list (or pointers). In linked list, every element is represented as nodes. A node consists of three fields such as : (a) Left Child (LChild) (b) Information of the Node (Info) (c) Right Child (RChild)

The following figure (Fig. ) shows the linked list representation of the binary tree in Fig

If a node has a left or/and right node, the corresponding L Child or R Child is assigned to NULL. The node structure can be logically represented in C/C++ as:

struct Node

int Info;

struct Node *Lchild;

struct Node *Rchild;

typedef struct Node *NODE;

OPERATIONS ON BINARY TREE

Ihe basic operations that are commonly performed an binary tree is listed below :

1.     Create an empty Binary Tree

2.     Traversing a Binary Tree

3.     Inserting a New Node

4.     Deleting a Node

5.     Searching for a Node

6.     Copying the mirror image of a tree

7.     Determine the total no: of Nodes

8.     Determine the total no: leaf Nodes

9.     Determine the total no: non-leaf Nodes

1   Find the smallest element in a Node

11 Finding the largest element

1   Find the Height of the tree

1   Finding the Father/Left Child/Right Child/Brother of an arbitrary node

Some primitive operations are discussed in the following sections. Implementation other operations are left to the reader.

======================

 Like and Share with Comment

======================