1
Data structures – SYCM – 2005-06 / 9422092905 / 2540017
Non Linear Data Structure- Trees
So far have studied linear type of data structure such as strings, arrays, stacks, queues and list. In this topic we will study non-linear data structure called a tree. Trees are used to represent the hierarchical relationship between individual data items.
Trees: Trees are non-linear data structure that represents the hierarchical relationship among individual data items.
E.g.: Family tree, records, an algebraic expression involving operators, classification of books in library, students record at a typical university, the hierarchy ofinstitution.
General structure of tree: Consider the example of student records. The student record have following field:
1)Name of student
2)Address of student
3)Course which student is doing
4)Exam appeared by student
5)Grade obtain by student.
Student in at highest level 0(zero) is called as root node called as parent node
-The name, address and course which are directly rooted to the parent node are called as child node. The level of child node is one level below (lower) than root node.Thus name, address, and course are level 1.
-The link between parent node to its child node is called as branch of tree.
-The root node of tree is ancestor of all nodes in the tree.
-A node that has no child is called a leaf. I.e. address, grade, exam are leafs.
-A tree consist of a number of subtrees in above fig. Node name is subset of tree that represent itself a tree.
If out degree of every node is exactly to m or zero then number of nodes at level I is mI-1 then the tree is called as full or complete m-ary tree.
Definitions related to trees
Tree
A tree may be defined as a finite set T of one or more nodes such that
(a) there is specially designated node called the root of the tree,
(b) the remaining nodes (excluding root) are partitioned into n >= 0 disjoint sets T1 ,T2 ,T3 and each of these set is a tree in turn. The trees T1 ,T2 ,T3 is called the sub-trees (or children) of the root. Note that the definition is recursive as the children of the root of a tree are tree once again.
A tree consist of a collection of nodes which are connected by directed arc. A tree contain a unique node called as Root. Root is the only node which does not posses parent.
A node which points to other nodes is said to be parent of the nodes to which it ispointing and these nodes in tree are called children of that node
Sibling
Nodes are called as sibling if they have same parent.
Ancestor
A node is called as ancestor of another node if it is parent of that node or the parent of the some other ancestor of that node. Root is ancestor of every node in the tree.
Leaf
A node that has no child is called a leaf.
Analysis of the Above Tree
Root / RaviChildren / Natasha , Kiran , Rahul / of Ravi
Children / Sunny , Honey / of Natasha
Children / Jaggi Sunil / of Rahul
Leaf or terminal node / Sunny , Jaggi , Kush , / Sunil
Sibling / Sunny Honey / Jaggi , Sunil
Parent / Natasha , Karan , Rahul
Ancestor / Ravi
Binary tree
It is special kind of tree which can be easily maintained in computer. A binary tree T is defined as finite set of element called nodes such as
1)T is empty (called the NULL tree or empty tree)
2)T contain a distinguished node R called the root T, and the remaining nodes of T form an ordered pair of disjoint binary tree T1 & T2.
In binary tree each element cannot have more than two child nodes i.e. has two subtrees (null or not-null) called as left and right subtree.
Root
Subtree
If in a tree out degree of every node is less than or equal to m then such tree is called as m-ary tree. If m=2 then the tree is called as binary tree.
If T does contain root R then two trees T1 and T2 are called respectively as left and right subtree of R. If T1 is not empty then it is called as left successor of R and T2 is not empty then it is called as right successor of R.
Definition: A binary tree is a finite set of element which is either empty(null) or consist of three adjacent subset. The first subset contain a single element called the root of the tree and remaining two subsets are called as left subtree and right subtree.
Analysis of above tree: Fig. Shows binary tree will letter from A through L. the absence of a branch indicate an empty or null subtree.
1)Root of tree is denoted by A.
2)Left subtree is rooted as B.
3)Right subtree is rooted as C.
4)Left of subtree of root A nodes B,D,E
5)Right subtree of root A nodes C,F,G
Nodes with no successor is called as terminal node.
Depth( height) and Level of Tree
Depth of the Tree
The Length of the longest path from root to any node is called as depth of the tree.
The depth of the binary tree can also be defined as the maximum level of any leaf in the tree.
Root A is at level 0 , Parent B , C are at level 1 ,D , E are at level 3. and so on. Root is at level 0 and the level of any other node in the tree is one more than the level of its parent.
Depth is one more than the level than the largest level number.In above example level is 3 and depth is 4
Example
In above tree
1)The left subtree of the binary tree rooted a C and right subtree of a binary tree rooted at E both are empty.
2)Binary tree rooted at D,F,I and J have empty right & left nodes.
3)D,F,I,J are called as leaf nodes.
4)The depth of a binary tree is the maximum level of any leaf in the tree. This equals the length of the longest path from root to any leaf.
Example: Represent the following algebraic expressions by means of binary tree.
E = (a-b) / ((c* d)+e)
Binary Tree
If the tree have maximum two children or node the it is called as binary tree.
A binary is the tree which is either empty or consist of a root node together with two children , a left sub tree and a right sub tree.
Some Examples of Binary tree
Strictly binary tree
If every non-leaf node in a binary tree has non-empty left and right subtree.
The tree is termed as strictly binary tree. Meaning that each node in the tree will have either 0 or 2 nodes.
Complete binary tree
Consider any binary tree T. each node of T can have at most two children. Hence at any level r of T can have at most 2r nodes. The tree T is said to be complete if all its, levels except possibly the last have the maximum number of possible nodes and it at all the nodes at the last level appears as far as possible.
Complete binary tree is defined as a binary tree whose non leaf nodes have non empty left and right subtree and all leaves are at the same level.
If a binary tree has the property that all elements in the left subtree of a node n are less than the contents of n and all elements in the right subtree are greater than the contents of n, such a binary tree is called the binary search tree.
As the name suggests, they are very useful for searching an element just as with binary search.
The total number of nodes in a completely binary tree of depth d is equal to sum of the number of nodes at each level between 0 and d is given by
Nt = 20 + 21 + 22 ---- +2d
= 2 * I
to determine the children and parents of node following formulae is used.
For any node K in any complete tree the
Left children = 2 * K.
Right children = 2 * K+1
The parent of K = K /2.
E.g.: the children of a node are 18 and 19 and its parent = 9/2 = 4. The depth of dn of complete tree Tn with node n is given by
Dn = log2n +1
E.g. : In complete binary Tn and it has n= 1000 000 then depth = 21
Binary Search Tree
A binary search tree is a binary tree which is either empty or contains anode whose key satisfies the conditions
(a) The key in the left child of a node (if any) preceeds the key in the parent node.
(b) The key in the right child of a node (if any) succeeds the key in the parent node.
(c) The left and right subtree of the root are again binary search trees.
Here, we are assuming that there are no duplicates which means that no two entries in a binary search tree can have equal keys. To accommodate the duplicates we can modify the definition so that the key in the right child of a node can be greater than or equal to the key in the parent node.
Representation of binary tree in memory
Binary tree represented in memory by two ways
1)Link representation (Link list using pointer or arrays)
2)Sequential representation. (Array)
1)Link representation of binary tree:
In linked representation doubly link list is used
for tree storage.
LPTR INFORPTR
Right child Data left child
Field Field Field
Each node contain three fields
1.Data field (info)
2.Left Child Field (Lptr)
3.Right Child Field (Rptr)
LPTR denotes the address of location of left subtree. RPTR denotes the address of location of right subtree. Empty subtree(leaf) are represented by pointer value NULL.
C language sample code
Struct bnode {
Char data ;
Struct bnode *left;
Struct bnode *right;
}
main()
{
struct bnode *T , *p, *q;
T = Null;
P = (struct *)malloc(sizeof(struct bnode) ;
p data = ‘A’ ;
p left = Null ;
pright = Null ;
T = p; P T now points to the root node of the tree /
q = T;
p = (struct *)malloc(sizeof( struct bnode) ;
p->data = ‘B’;
p->Ieft = p->right NULL;
q->Ieft = p;
q = p;
p = (struc bNode *)malloc(sizeof(struct Nocie));
p->data =
p->left = p->right = NULL;
q->left = p;
q = p;
p = (struc bNode *)malloc(sizeof(struct Nocie));
p->data = ‘G’
p->Ieft = p->right = NULL;
q->right = p;
q = T /* q now points to the node ‘B’ /
p = (struct *)malloc(sizeof( struct bnode) ;
p->data = ‘E’;
p->Ieft = p->right NULL;
q->right = p;
q = p;
p = (struc bNode *)malloc(sizeof(struct Nocie));
p->data = ‘H’
p->Ieft = p->right = NULL;
q->left = p;
q = p ;
q = T
p = (struct *)malloc(sizeof( struct bnode) ;
p->data = ‘E’;
p->Ieft = p->right NULL;
q->right = p;
q = p;
p = (struc bNode *)malloc(sizeof(struct Nocie));
p->data = ‘F’
p->Ieft = p->right = NULL;
q->left = p;
q = p ;
p = (struc bNode *)malloc(sizeof(struct Nocie));
p->data = ‘T’
p->Ieft = p->right = NULL;
q->right = p;
Representation of tree using Arrays ( two dimensional)
For tree representation three parallel arrays are used info, left and right. For all each nodes N of T will correspond to a location K such that
1)INFO[k] contain data at the node N
2)LEFT[k] contain the location of the left child of node N.
3)RIGHT[k] contain the location of the right child of node N.
4)
Root5
Available
8 / INFO / LEFT / RIGHT
1
2 / C / 8 / 13
3 / D
4
5 / A / 10 / 2
6 / E
7
8 / F
9
10 / B / 3 / 6
11
12
13 / G
14
Example of Two dimensional Array representation of Link List
Example of One dimensional Array representation of Link List
Advantages of link list storage
1)Most appropriate and efficient , more popular
2)Easy to insert, delete the element.
3)Can be easily altered in size by using wasted memory space in reformulation of a binary tree.
Disadvantages
1)Memory space is wasted in NULL pointer.
2)It is difficult to determine parent node from its given node.
3)It is more difficult to offer dynamic storage in language such as COBOL, PASCAL, BASIC, FORTRAN etc.
2) Sequential representation of binary tree
The tree T can be represented using only single linear array such representation in memory is called as sequential representation of T(tree).
This representation uses only a single linear array TREE as follows:
1)The root R of T is stored in Tree[1].
2)If node N occupies Tree[k] then its left child is stored in Tree[2* k] and its right child is stored in tree[2*k+1].
3)NULL is used to indicate a empty tree.
1 / A / 14 / I2 / B / 15
3 / C / 16
4 / D / 17
5 / E / 18
6 / 19
7 / F / 20
8 / 21
9 / G / 22
10 / H / 23
11 / 24
12 / 25
13 / 26
Fig. Shows Sequential representation of the Tree
the depth of tree will require an array with approximately 2d+1 elements.
E.g.: For a complete tree, it has 11 nodes & depth = 5 will require
25+1 = 26 = 64 elements.
Advantages of sequential representations:
1)Simple to determine parent node from a given child. If child is at location N in array then parent node is at N/2 (integer division.)
2)It can be implemented easily in language which supports static allocation of memories i.e. arrays like basic, Fortran, Pascal.
3)Searching and finding of element is easy.
Disadvantages:
1)A large amount memory is wasted due to partially filled tree.
2)Excessive amount of processing time is required to move the considerable data up & downwards.
3)Difficult to insert and delete element.
Example : Storage for the Equation E =(a-b)+(c*(d/e))Sequential Storage :
1 / “+” / 92 / “-” / 10
3 / “*” / 11
4 / “a” / 12
5 / “b” / 13
6 / “c” / 14 / “d”
7 / “/” / 15 / “e”
8 / 16
Operation on tree
There are many operations performed on binary tree structure such as
1)Traversal
2)Insertion
3)Deletion
4)Searching
5)Copying
Traversing the binary tree
There are three standard ways of traversing a binary tree T with root R. These three algorithm are
1)Preorder
2)In-order
3)Post-order
1) Preorder Traversing
1)Process the root R
2)Traverse the left subtree of R in preorder
3)Traverse the right subtree of R in preorder.
In preorder traversing root R is processed before the subtree are traversed. Hence this algorithm is sometimes also called as Node-left-right or depth first order.
The preorder traversal of tree T is ABCDEFGHIJK. Note that left subtree of root A is traversed before the right subtree and both are traversed after A.
Example
Consider example
[(a+(b-c))] * [(d-e)/(f +g-h)] Infix
[a+(-bc)] * [(-de)/(+fg -h)]
[+a(-bc))] * [(-de)/(-+fgh)]
*[+a(-bc)]0/(-de)(-+fgh)]
*+a - bc / -de + - fgh Prefix
Algorithm: Preorder traversal of binary tree
Algorithm RPREORDER(T)
T = Pointer variable which holds the address of node of binary tree.
LPTR = Point to left subtree.
RPTR = Point to right subtree.
This algorithm traverse the tree in preorder in a Recursive manner
1)Process of root node
If ( T > NULL) then
Write (Data(T))
Else
Write('Empty tree');
Return.
2)Process left subtree
If (LPTR(T) >NULL) then
Call RPREORDR(LPTR(T))
3)Process right subtree
If (RPTR(T) >NULL) then
Call RPREORDR(RPTR(T))
4)Finished
Return
Non-recursive or iterative methods for Preorder traversal:
General algorithm for preorder traversal binary tree
1)If the tree is empty then
Write ('Tree empty');
Return
Else
Place the pointer to the root of the tree on the stack
2)Repeat step 3 while stack is not empty
3)Pop the top pointer off the stack
Write the data associated to the node
If left subtree is not empty then
Stack the pointer to the right subtree
Set pointer to the right subtree
Procedure :
1)Initialize
If T = NULL then
Write ('Empty tree');
Return
Else
Top 0
Call push(s, top, T)
2)Process each stacked branch address
Repeat step 3 while top > 0
3)Get stored address and branch left
P pop(s, top)
Repeat while P> NULL
Write (data(P))
If(RPTR(P))> NULL) then
Call push(s, top, RPTR(P))
Store address of non empty right subtree
P LPTR(P) branch left
4)Finished
Return.
Inorder Traversing
1)Traverse the left subtree R in order
2)Process root R
3)Traverse the right subtree
In the algorithm the root R is processed in between the traversal of the subtrees. Hence it is also called as left-node-right traversal.
The In-order traversal of T is DBEAFCG.
Algorithm: Inorder(Root) [Recursive algorithm]
Root Contain the address of root node of tree
Left_PTR Point to left subtree of tree.
Right_PTR Point to right subtree of tree.
Info(root) Data field.
1)Check for empty tree
If (root =NULL) then
Write('Empty tree');
Return.
2)Traverse the left subtree
If (Left_PTR(root)>NULL) then
Call Rinorder(left_PTR(root))
3)Visit the root node
Write(info(root))
4)Traverse the right subtree
If(Right_PTR(root)>NULL) then
Call Rinorder(Right_PTR(root))
5)Finished
Return
Non recursive Inorder traversal algorithm
Algorithm NRINORDER(root)
Root Contain root address of binary tree.
Stack Vector
Top Top element pointer by top
PTR Current element in tree
1)If (root = NULL) then
Write("empty tree')
Return
Else
Top 0
Call push(stack, top, root)
2) Repeat step 3 while stack is not empty
Repeat step 3 while (top>0)
3)If root >NULL then
Call push(stack, top, root)
PTR left_PTR(root)
Else
Call pop(stack, top, root)/* No more left subtree */
If not empty then
Write(info(PTR))
PTR right_PTR(root)
4)Finished
Return
Postorder Traversal
1)Traverse the left subtree of R in Post-order
2)Traverse the right subtree of R in Post-order
3)Process of root R.
In this algorithm the root R is processed after subtree are traversed, it is called as left-right-node traversal.
The traversal way is DFBFGCA i.e. Postorder traversal.
The algebraic expression
[a+(b-c)] * [(d-e)/(f + g-h)]
[a+(bc-)] * [(de-)/(fg+)-h)]
(abc-+ ) * [(de-)/ (fg + h) -]
(abc-+) * [de- fg + h-)] /
abc - + de - fg + h /* Postfix
Equation (a-b) + (c*(d/e))
ab - cde /* + Postfix
Recursive algorithm for Postorder traversal of a binary tree
Procedure RPOSTORDER(T)
T = tree starting address
1)Check for empty tree
If T = NULL then
Write ('Empty tree');
Return.
2)Process let subtree
If (LPTR(T) >NULL) then
Call RPOSTORDER(LPTR(T))
3)Process the right subtree
If (RPTR(T)>NULL) then
Call RPOSTORDER(RPTR(T))
4)Process the root node
Write (data(T))
5)Finished
Return.
Non-recursive algorithm for Postorder traversal
Algorithm NRPOSTORDER(root)
Root = Contain the root address of binary tree
Stack = Vector
Top = Top element of stack pointed by top
PTR = Current element in tree.
1)If the tree is empty then
Write('Empty tree'); return
Else
Initialize the stack & pointer value to root node of tree.
If (root =NULL) then
Write('Empty tree');
Return.
Else
PTR root
Top 0
2)Start an infinite loop that traverse in post order to repeat through step 5
Repeat step 5while(true)
3)Repeat while pointer value is not NULL set the pointer value to left subtree
Repeat while(PTR> NULL)
Call push(stack, top, PTR)
PTR left_child(PTR)
4)Traverse left and right subtree of node repeat while top pointer on stack is negative. Pop pointer off stack and write data associated with positive value of this pointer
Repeat while(stack(top)<0)
PTR pop(stack, top)
Write(info(PTR))
If(top=0) then
Return
5)Set pointer value to right subtree of the value of the top of stack. Stack is negative value of pointer to right subtree
PTR right_child(stack(top))
Stack(top) (-stack(top))
Insertion of node in binary tree