Binary tree and operations

binary tree and their operations

1. Binary tree and operations v.lavanya MSC I T

2. OBJECTIVES BASIC TERMINOLOGY BINARY TREES PROBERTIES OF BINARY TREE REPRESENTATION OF BINARY TREE LINEAR USING(ARRAY) REPRESENTATION NON-LINEAR USING(LINKEDLIST)REPRESENTATION OPERATIONS OF BINARY TREES INSERTION DELETION TRAVERSAL MERGING

3. node : MAIN COMPONENT of any tree structure a no de of tree stores the actual data and links to oter nod e parent: The parent of the node is te imediate predecessor of the node Root : root node is desigated wich has no parent child: if th e imediate predecessor of the node is parent of the node then all imediate sucessor of a node are known as child the child which is on left side is called left child and hat on right side is called right child leaf: the node which is at the end and does not have any child is called leaf node is also called terminal node a binary tree contains node , parent,child,link ,root,leaf,level,heigt,degree,siblings.... Basic terminolgies

4. what is a binary tree A binary tree is special form of a tree a data structure iN BINARY TEE left branch when greater and the right when less than thE NODE In binary tree they are two types complete binary tree anf full binary tree complete binary tree; A complete binary tree is a binary tree in which every level except possible the last is completely filled and alll notes full binary tree : A binary tree is a full binary tree if it contains the maximum possible number of ndes at all levels

5. BINARY TREES WITH EXAMPLES

6. PROPERTIES OF BINARY TREE A Binary tree can have a maximum of 2 power l nodes at level of l if the level of the root is zero 2power of 0=1 2 power of 1=2 2 power of 2=4 2 power of 3=8

7. properties of binary trees the maximum no of nodes possible in a binary tree of height h is 2power of h-1 The minimum no of nodes possible in a binary tree Height h is h a binary tree has the minimum no of nodes one every parent has one child such kind of trees are called skew binary trees

8. Representation of Binary trees a binary tree must represent a hierarical relationship between a parent node and child nodes there are two methds ONE IS LINEAR REPRSENTATION USING ARRAY ANOTHER ONE IS NONLINEAR REPRESENTAION USING LINKED LIST

9. LINEAR REPRESENTATION OF BINARY TREE The root N of T is stored in TREE [1]. If a node occupies TREE [k] then its left child is stored in TREE [2 * k] and its right child is stored into TREE [2 * k + 1] for exaample(a-b)+c*(d/E)

10. A dvantage disadvantage sequential Representation Advantage of sequential rpresentation any node can acessed from any other node by calculating the index value data are stored without any pointers to their sucessor and ancestor which are mentioned implicity programing lanuage where dynamic memmory allocation is not possible such as(BASIC ,FORTRAIN)ARRAY REPREPRESENTAION IS nly means to store a tree

11. disadvantage sequential representation Disadvantage of sequential reprentation other then the full of binary trees the majority of the array entries may be empty it allows only static representation it is in no way possible to enhance the tree structure if the array size will be limited insering new node to the tree or deleting a node in a tree data moved up and moved down in an array excessive amount of processing time

12. linked representation of binary tree linked list representation of a binary tree they are two field s to stor the address of left child and right child of the node data is the current information of the node if one knows the address of the root node then form it other node can be acessed

13. physical implementation of a binary tree in memmory to build an a tree using array and l iked list using algorithms The algorithm build a tree is build a tree using an array of element type to insert a DATA Algorithm build a tree input:ITEM is the data contet of the node i output: a binary tree with two sub-trees of the node i data structure: array representation of a binary tree

14. operations of a binary tree operations of binary trees insertion: TO include a node into an existing binary tree deletion: TO delete a node from a non-empty binary tree Traversal: TO visit all the nodes in abinary tree in traversal they are three orders inorder -> LEFT->ROOT->RIGHT preorder -> ROOT->LEFT->RIGHT postorder-> LEFT->RIGHT->ROOT merge:TO merge two binary trees into a large one

15. insertion operation in binary tree in this operation to insert a new node at any position in a binary tree we have a simple insertion for ex to insert a “g “ a new node two stops search the existence node second establish the link

16. Algorithm insert a binary tree in array format algorithm insert a binary tree using array input:KEY be the data of a node inserted with item output:newly inserted node with data item as a left or right child of the node with data KEY data structure:array A storing a binary tree

17. insert a binary tree using linked list insert:KEY is the data content of the key node after new node is to be inserted an ITEM is the data content of the new node can be inserted output: A node with data component ITEM inserted as an extrernal node after the node having data KEY if such a node does not exist with empty (s), that is, eiter child or both children IS/ARE ABSENT. DATA STRUCTURE: linked structure of a binary tree. ROOT is the pointer to the root node.

18. algorithm steps: ptr = search_link(ROOT,KEY) IF (ptr = NULL) then print “search is unsuccessful: no insertion” EXIT ENDIF IF(ptr->Lc =NULL) or (ptr-.rc=NULL) read option to inseet as left (L) or right (r) child (give option=l/r) IF (ptr-.LC =NULL) then new =GETCODE(NODE) New->DATA =ITEM new->LC = new-->RC = NULL ptr->LC = new ELSE

19. algorithm PRINT “ insertion is not possible as left child” EXIT EDIF ELSE IF(pf->RC =NULL) new=GETNODE new->DATA=ITEM new->LC=new->RC=NULL ptr->RC=new else print”insertion is not possibble as right child” exit end if else print”the key node is already has a child” stop

20. deletion in deletion operation can be carried out of two kinds of storage representation of binary trees in ordernto delete a node in a binary tree it is required to reach at the parent node to be deleted the link of the parent nodes whih stores the location of the node to be deleted is then set buy a NULL entry input :given ITEM as data of the node with which the node can be identified for deletion output :a binary tree without a node having a data ITEM data stucture : array a storing binary trees SIZE denotes the size of a

21. Deletion algorithm using array

22. Traversal WHAT IS A TRAVERSAL? THE traversal operation is frequently used operation of a binary this operation to visit each node in the tree exactly once a full traversal of a binary tree gives a linear ordering of the data in the tree if a binary tree contains an arithmetic expression then it traverse infix notations,posfix notations,prefix notations preorder traversal postorder traversal inorder traversal

23. preorder traversal in this traversal root is visited first then the left sub-tree in preorderand the right sub-tree in preorder fashion visit the Root node R Traverse the LEFT SUB-TREE of R in preorder traverse the RIGHT SUB-TREE OF R IN PRE ORDER Algorithm of preorder input:ROOT is the ptr output:visit the all the nodes in preorder data structure:linked structure of a binary tree ptr=ROOT IF(ptr=\ NULL)THEN VSIT(PTR) preorder(ptr->LC preorder(ptr-?RC) endif stop

24. postorder Traversal ROOT node is visited at the end fist visited left sub-tree and right sub tree last ly the root Traverse the left sub tree of the root R in the postorder Traverse the right sub tree of the root R in postorder visit the root node R algorithm postorder input: ROOT is the ptr to root node of the biary tree output : visiting all the nodes in preorder fashion data structure :linked structure of the binary tree ptr=ROOT if(ptr=!NULL)THEN postorder(ptr->LC) postorder(ptr->RC) visit(ptr) Endif stop

25. INORDER TRAVERSAL in this inorder traversal before visiting the root node left tree is visited and after visit right node Traverse the left sub-tree of the Root node r in inorder visit the Root node R Traverse Right sub-tree of the root node r in inorder ALGORITHM inorder input:ROOTnode is the ptr of the root node of a binary tree output:visiting all the nodes in inorder fshion data structure:linked structure of a binary tree ptr=Root if(ptr=!NUL)then inorder(ptr->LC) VISIT(PTR) inorder(ptr->RC) Endif stop

26. merging two binary trees another fundamental operation that is possible is the merge operation this ooperation is applicable to trees which are representing using LINKED STRUCTURE THERE ARE TWO WAYS T1 AND T2 ARE TWO BINARY TREES CAN BE MERGED WITH T1 IF MERGING TWO BINARY TREES USING COMPATIBLITY

27. ALgorithm of two merge the binary treeinto one input:two pointers ROOT1 and ROOT2 OF THE TWO BINARY TREES t1,t2 output:a binary treee containing all the node t1,t2 ptr to the root as ROOT data structure:linked the data strucure steps: if(ROOT1=NULL)THEN ROOT=ROOT2 EXIT

28. THANK YOU