tree Data Structures in python Traversals.pptx

It is all about trees

1. TREE DATA STRUCTURE EXAMPLE: COMPUTER FILE SYSTEM

2. A HYPOTHETICAL FAMILY TREE

3. A tree consists of a finite set of elements, called nodes, and a finite set of directed lines, called branches, that connect the nodes. TREE ADT Tree is a non- linear data structure which organizes data in recursive hierarchical structure. In tree data structure, every individual element is called as Node . Node in a tree data structure stores the actual data of that particular element and link to next element in hierarchical structure.

4. STRUCTURE OF A TREE There is one and only one path between every pair of nodes in a tree.

5. TREE TERMINOLOGY

6. ROOT NODE In a tree data structure, the first node is called as Root Node . Every tree must have a root node. In any tree, there must be only one root node .

7. EDGE The connecting link between any two nodes is called as EDGE . In a tree with ' N ' number of nodes there will be a maximum of ' N- 1 ' number of edges.

8. PARENT NODES

9. CHILD NODES

10. ANCESTOR AND DESCENDANT Ancestors: Any node in the path from the current node to the root node. Descendant: Any node in the path from the current node to the leaf nodes.. Ancestor(J) = E,B,A Descendant(C) = G,K,H

11. SIBLINGS

12. LEAF NODES The leaf nodes are also called as External Nodes or Terminal Nodes

13. INTERNAL NODES

14. DEGREE The Degree of a node is total number of children it has. The highest degree of a node among all the nodes in a tree is called as ' Degree of Tree '

15. LEVEL In a tree each step from top to bottom is called as a Level and the Level count starts with '0' and incremented by one at each step. Level- distance from the root node.

16. HEIGHT Height of all leaf nodes is 0.

17. DEPTH Depth of the root node is '0'

18. PATH Length of a Path is total number of edges in that path.

19. SUBTREE Each child node with a parent node forms a subtree recursively . Any connected structure below root is a subtree. Collection of subtrees makes a tree.

20. FOREST A forest is a set of disjoint trees .

21. COMPARISON

22. ReoI Leeł Noda &aval0 Levei 1

23. APPLICATION OF TREE

24. CLASSIFY THE TWO TRAVERSALS PERFORMED IN TREE ADT. A traversal of a tree requires that each node of the tree be visited once A typical reason to traverse a tree is to display the data stored at each node of the tree Traversal Types preorder Inorder Postorder level-order

25. LEVEL ORDER TRAVERSAL

26. Traversal Starts at the root node and explores as deep as possible along each branch and backtrack to sibling branch until all nodes are visited. It is a recursive approach for all subtrees.

27. PREORDER TRAVERSAL Processing order: Root → Left → Right Algorithm Visit the root Traverse the left sub tree i.e. call Preorder (left sub tree) Traverse the right sub tree i.e. call Preorder (right sub tree)

28. EXAMPLE

29. Traverse the entire tree starting iron the root rode keeping yourself to the left. Preorder Traversal : A , B , D , E , C , F , G

30. INORDER TRAVERSAL Processing order: Left → Root → Right Algorithm Traverse the left sub tree i.e. call Inorder (left sub tree) Visit the root Traverse the right sub tree i.e. call Inorder (right sub tree)

31. EXAMPLE

32. POSTORDER TRAVERSAL Processing order: Left → Right → Root Algorithm Traverse the left sub tree i.e. call Postorder (left sub tree) Traverse the right sub tree i.e. call Postorder (right sub tree) Visit the root

33. EXAMPLE

34. Postorder Traversal Shortcut

35. EXERCISE

36. Q1 1. Visit the following tree in a breadth first manner and print all the nodes.

37. ANSWER

38. Binary Tree Expression Tree Binary Search Tree Trees AVL Tree B Tree Heap Tree TYPES OF TREES

39. BINARY TREE AND ITS RELATED OPERATIONS A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. A Binary Tree node contains following parts. Data Pointer to left child Pointer to right child

40. BINARY TREE A node can have 0,1, and 2 children in a binary tree

41. CONT.. In a tree each node contains information and may or may not contain links.

42. PROPERTIES OF BINARY TREE At any level ‘i’, maximum number of nodes possible is 2^i

43. Maximum number of nodes of height h= CONT..

44. Minimum number of nodes of height h=h+1 CONT..

45. CONT.. Maximum height of the tree if minimum number of nodes is given is (n- 1)

46. CONT.. Minimum height of the tree if maximum number of possible nodes is given by

47. TYPES OF BINARY TREE Full/Strict/ Proper Binary Tree Complete Binary Tree Perfect Binary Tree Degenerate Binary Tree Balanced Binary Tree Unbalanced Binary Tree

48. FULL BINARY TREE It is a binary tree where each node will contains exactly two children except leaf node

49. Full Binary Tree

50. COMPLETE BINARY TREE It is a binary tree where all levels are completely filled (except possibly the last level) and the last level has nodes as left as possible

51. Complete binary tree

52. PERFECT BINARY TREE It is a binary tree where all internal nodes have 2 children and all leaves are at same level A perfect binary tree is a complete binary tree or full binary tree but vice versa is not true

53. DEGENERATE BINARY TREE It is a binary tree where all internal nodes are having only one child

54. BALANCED BINARY TREE Find Balance Factor, B=H L - H R H L - height of left subtree; H R - height of right subtree The height of the left and right subtrees differs by no more than one i.e., its balance factor of every node should be –1, 0, or +1

55. UNBALANCED BINARY TREE