Binary Tree and Operations on Binary Tree

Tree is a non linear data structure which consists of non-empty set of vertices ( or nodes ) and a set of edges where each nodes are connected to each other with no multiple edges or loops (i.e. no simple circuits)

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root and other two are left and right sub trees which can be also empty. Each element of binary tree is called node of the tree. OR, a rooted tree is called binary tree if every internal vertex has no more than two children.

In figure,

• A is father of B & C
• B is left son of A & C is right son of A
• Two nodes are brothers, if they are left and right son of the same father.
• Direction from root to leaves is “down” and reverse is “up”. It grows downward not like that of natural tree.

Operations on Binary tree

There are number of primitive operations that can be applied to a binary tree. If p is a pointer to a node nd of  a binary tree, then

• info(p) returns contents of node nd.
• Functions left(p), right(p), father(p) and brother(p) returns pointers to the left son, right son, father and brother of node nd respectively.
• logical functions isleft(p) and isright(p) returns value true if node nd is left or right son respectively otherwise returns false.
• maketree(x) creates  a new binary tree consisting of single node with information field x and returns a pointer to that node.
• setleft(p,x) crrates a new left son of node(p) with information field x.