Binary Tree (Strictly, Complete,Transversal binary tree)

Binary tree is a tree

which is either empty or consists of node called root node and two disjoint subtrees known as left subtree and right subtree which are again binary tree. So in a binary tree no node can have more than two children.

Fig: binary tree

Strictly Binary Tree

Strictly binary tree is a tree where every internal node has non empty left subtree and right subtree. So in a strictly binary tree every node must have either zero or two children.

 

  Fig:  Strictly binary tree 

Complete (full) Binary Tree

A complete binary tree is a strictly binary tree for which all the leaf nodes are at the same level.

 

Implementation of Binary tree

To represent a binary tree in computer memory a doubly linked list is used. In this representation all nodes of binary tree acquired storage location in memory. Every node maintain three information as address of left child, information of the node and address of right child.

Therefore a binary tree can be defined using a structure as:

Struct Node

{

            Data_type info;

            Node *left;

            Node *right;

};

The binary tree can be represented in computer memory as:

Traversal of binary tree

It means visiting every node of the binary tree only once. In many applications it is necessary to move through all the nodes of binary tree only once. If there are n nodes in a binary tree then there are different orders in which all the nodes can be visited. We consider only three traversal order depending on the order in which they visit a root node.

1.      Pre-order traversal (Root-left-right)

2.      In-order traversal (left-root-right)

3.      Post-order traversal (left-right-root)

1.      Pre-order Traversal

To traverse a non empty binary tree in preorder which is also known as depth first order, we perform the following three operations.

·         Visit the root node

·         Traverse the left subtree in pre-order

·         Traverse the right subtree in preorder.

• Preorder (NLR) traversal yields: 2, 7, 2, 6, 5, 11, 5, 9, 4
• Postorder (LRN) traversal yields: 2, 5, 11, 6, 7, 4, 9, 5, 2
• In-order (LNR) traversal yields: 2, 7, 5, 6, 11, 2, 5, 4, 9