Binary Tree Concept and Abstract Data Type of Binary Tree

A binary tree is a finit set of nodes which is either empty or consisits of a root and two disjoint trees called left subtree and right subtree .
In Binary tree each node will have one data field and two pointer fields for reperesenting the sub-branches . The degree of each node on the binary tree will be at the most two .

Abstract Data Type of Binary tree 

ADT Binary Tree

Operations :

    buildBtree() : Creates a binary tree

    leftchild(t) : Returns the Left child of t

    rightchild(t): Returns the right child of t.

    empty()      : Returns true if the tree is empty false otherwise

    size()       : Returns the number of nodes in the tree

    preorder()   : Displays the binary tree in preorder

    inorder()    : Displays the binary tree in inorder

    postorder()  : Displays the binary tree in postorder

    levelorder() : Displays the binary tree in level order

Properties if Binary Trees

Property 1

A Binary Tree with n elements , has exactly n-1 edges where n>0
Proof :
Every node in a binary tree , except the root node , has exactly one parent . There will be exactly one edge between each child and its parent . So the number of edges of binary tree with n nodes is n-1 .

Property 2

A binary tree of height h , h>0 has minimum of h and maximum of 2^h -1 elements in it .

Property 3

If a binary tree has n nodes we can construct binary tree with maximum height of n and with minimum height of log(n+1) .

Array Representation of binary tree :

When the elements of a binary tree are represented in the form of an array , the representation is known as an formula based repesentation . The elements are represented or stored at the array locations relative to the numbers assigned to them.
          In the array approach the nodes are stored in an array and are not linked by references . The position of the node in the array corresponds to its position in the tree .The node at index 0 is the root the node at index 1 is the roots left child the node at index 2 is the roots right child and so on progressing from left to right along each level of the tree .

Every position in the tree corresponds to a cell in the array , whether it represents an existing node or not . Adding a node at a given position in the tree means inserting the node into the equivalent cell in the array . with this scheme , a node's index number in the array . If a node's index number is index , then this node's left is at (2*index +1) position. Its right child is at , (2*index+2) position . And its parent is at , ((index-1)/2) position . 

In most situations representing a tree with an array is not very efficient . Unfilled nodes and deleted nodes leave holes in the array wasting memory . Even worse when deletion of a node involves moving subtrees every node in the subtree must be moved to  its new loaction in the array , which is time consuming in large trees . However if deletions are not allowed then the array representation may be useful especially if representation may also be useful in special situations . The tree in the workshop applet , for example is represented internally as an array to make it easy to map the nodes from the array to fixed locations on the screen display .  
Also check : Program for stack using arrays 

Also check : Program for Queue using arrays

Linked Representation of a Binary Tree :

Since binary tree consists of nodes which can have at most two children (left child and right child ) and obvious linked representation of such a tree involves having storage nodes . where left and right denote memory locations represented by NULL values .The data specify the information associated with a node . In real situations the data field may contain more than one data item .

Also check : Program for Stack using LinkedList

Also check : Program for Queue using LinkedList

Types of binary trees :

Full binary Tree :

A binary tree of depth k ( height k+1 ) has exactly 2^(k+1) -1 nodes is called a full binary tree .
Complete Binary tree :
A complete binary tree of (height h ) satisfies the following :

• Level 0 to h-1 represent a full binary tree of height h-1 .
• One or more nodes in level h-1 may have 0 or 1 child .
• If j,k are nodes in level h - 1 , then j has more child nodes than k if and only if j is to the left of k.

Common Binary Tree operations :

The following are various operations that we can perform on binary tree ,

• Determine the height
• Inserting a node into binary tree .
• Deleting a node from the binary tree
• Determining the number of elements in it .
• Displaying the binary tree
• Make a copy of binary tree
• Determining whether a tree is identical to other .
• If it is an expression tree evaluate the expression
• Deleting the total tree
• Searching for a node in the tree using different traversal techniques .

Final Words !

If I have missed any concept of Binary Tree Please get it to me through comments .