notesCHAPTER_5_tree_data_structure_ds.pppt

data structure, tree

1. T opic 5 TREE DFC 30233 DATA STRUCTURE

2. 1.0 Define tree,binary tree and binary search tree BINARY TREE A type of data structure where each parent node can have at most two child nodes These two child nodes are known as the  left child  and  right child .

3. 1.0 Define tree,binary tree and binary search tree BINARY SEARCH TREE A binary search tree is a binary tree in which the nodes are assigned values, with the following restrictions ; No duplicate values Left child node is smaller than its parent Node Right child node is greater than its parent Node

4. DID YOU KNOW?

5. ― Irene M. Pepperberg

6. 1.2 Terminology in relation to trees: Root , Parent , Children , Leaves, Sibling , Node , Path , Degree , Level

7. Root ROOT NODE - the first node root node is the origin of tree data structure must be only one root node Terminology: 1. Root

8. Parent Node PARENT NODE - the node which is predecessor of any node the node which has branch from it to any other node Terminology: 2. Parent

9. Child Child Node - the node which is descendant of any node the node which has a link from its parent node any parent node can have any number of child nodes all the nodes except root are child nodes Terminology: 3. Children

10. Leaf LEAF Node - the node which does not have a child leaf node is also called as Terminal node Terminology: 4. Leaf

11. Siblings SIBLINGS - nodes which belong to same Parent Terminology: 5. Siblings

12. Internal Nodes INTERNAL Node - the node which has at least one child Internal nodes are also called as ' Non-Terminal ' nodes Terminology: 6. Internal Nodes

13. Path PATH - the sequence of Nodes and Edges from one node to another node Length of a Path is total number of nodes in that path. Example: the path A - B - E - J has length 4 Terminology: 7. Path

14. Degree PATH - the sequence of Nodes and Edges from one node to another node Length of a Path is total number of nodes in that path. Example: the path A - B - E - J has length 4 Terminology: 8. Degree

15. Edge EDGE - the connecting link between any two nodes In a tree with ' N ' number of nodes there will be a maximum of ' N-1 ' number of edges. Terminology: 9. Edge

16. Level LEVEL - each step from top to bottom the root node - Level the children of root node - Level 1 Terminology: 10. Level

17. Height height of all leaf nodes is '0' Terminology: 11. Height

18. Depth height of all leaf nodes is '0' Terminology: 12. Depth

19. Terminology: 13. Sub Tree

20. 2.0 Binary Tree. Binary Tree is a tree in which every node can have a maximum of two children. Every node can have either children or 1 child or 2 children but not more than 2 children.

21. Full Binary Tree Binary Tree

22. Perfect Binary Tree Complete Binary Tree obtained from a perfect binary tree by deleting consecutive leaves of the tree from right to left 23

23. Arithmetic Expression

24. Example: arithmetic expression tree for the expression (2 × (a - 1)) + (3 × b) :

25. Infix, Prefix and Postfix traversal An infix expression , the operator appears between its operands. In a prefix expression, places a binary operator before its operands. In a postfix expression, the binary operators comes after its operands.

26. Example 1 S t a t e the o r de r o f node s v i s i t ed us i n g p r e f i x , i n f i x and postfix traversal. Prefix: - 8 / 4 2 Infix: 8 – ( 4 / 2 ) Postfix: 8 4 2 / -

27. Example 2 State the order of nodes visited using prefix, infix and postfix traversal. Infix form: Prefix form : Postfix form :

28. (x+xy) + (x/y) x+ ((xy+x)/y) Represent the expressions using binary trees. Write these expressions in prefix notation. Write these expressions in postfix notation. Write these expressions in infix notation.

29. Binary Tree Representations A binary tree data structure is represented using two methods. Those methods are as follows. Array Representation Linked List Representation Consider the following binary tree.

30. 1. Array Representation 2. Linked List Representation