Session 14: Trees

Session 14

Trees

1

Session Objectives • To understand the concepts of trees. • To know different parts of trees.

2

Session Topics • • • • • •

Introduction to trees Parts of trees Binary trees In-order Transversal Post-order Transversal Threaded Binary Tree 3

Definition of a Tree A directed tree is an acyclic graph, which has only one node with indegree 0 (root) and all other nodes have indegree 1. Indegree  the number of edges incident on a node . Outdegree  the number of edges leaving a node.

4

Parts of a Tree

5

Parts of a Tree nodes

6

Parts of a Tree parent node

7

Parts of a Tree parent node

child nodes

8

Parts of a Tree parent node

child nodes

9

Parts of a Tree root node

10

Parts of a Tree leaf nodes

A node that has an outdegree of 0, is called a Leaf node or Terminal node.

11

Parts of a Tree sub-tree

12

Parts of a Tree sub-tree

13

Parts of a Tree sub-tree

14

Parts of a Tree sub-tree

15

Level & Height of a Tree Level It is number of edges in the path from the root node Ex: Level of 25 is 2, Level of 10 is 0 Height It is one more than the maximum level in the tree. Ex: Height of tree shown below is 3.

10 20

15 30

25 16

Binary Tree A tree in which outdegree of each node is less than or equal to two is called a Binary tree. If the outdegree of every node is either 0 or 2, it is called Strictly Binary Tree.

17

Storage representation of a node In a linked allocation technique, a node in a tree has three fields. infowhich contains the actual information llinkwhich contains address of the left subtree rlinkwhich contains address of the right subtree A node can be represented as a structure as follows struct node { int info; struct node *llink; struct node *rlink; }; 18

Various operations performed on Trees • Insertion Insert a given item into a tree • Traversal Visiting the nodes of the tree one by one • Search Search for the specified item • CopyingTo obtain exact copy of the given tree • Deletion To delete a node from the tree

19

Traversals Traversal is the most common operation that can be performed on trees. There are three types of traversals:• Preorder • Inorder • Postorder

Preorder Traversal Recursive definition of Preorder traversal • • •

Process the root Node[N] Traverse the Left subtree in preorder[L] Traverse the Right subtree in preorder[R] 20

Example: Preorder A

B

D

G

H

C

E

I

F

A B

C

D G

E H

F

I

21

Function for preorder traversal void preorder(NODE root) { if(root != NULL) { printf(“%d”,root->info); preorder(root->llink); preorder(root->rlink); } } 22

Inorder Traversal

• • •

Traverse the Left subtree in inorder[L] Process the root Node[N] Traverse the Right subtree in inorder[R]

23

Example: Inorder G

D

H

B

A

E

I

C

F

A B

C

D G

E H

F

I

24

Function for inorder traversal void inorder(NODE root) { if(root != NULL) { inorder(root->llink); printf(“%d”,root->info); inorder(root->rlink); } } 25

Postorder Traversal • • •

Traverse the Left subtree in postorder[L] Traverse the Right subtree in postorder[R] Process the root Node[N]

26

Example:Postorder G

H

D

B

I

E

F

C

A

A B

C

D G

E H

F

I 27

Function for postorder traversal void postorder(NODE root) { if(root != NULL) { postorder(root->llink); postorder(root->rlink); printf(“%d”,root->info); } }

28

Insertion Algorithm to insert an item into a tree • Create new node for the item. • Find a parent node according to the directions given. • Find the appropriate position to insert the node • Attach the new node as a leaf.

29

Insert Example:

57 43 31

64

20

40 28

33

56 47

89 59

30

Insert 57

Example:

43 31

64

20

40 28

33

56 47

89 59

57 31

Binary Search Tree A binary search tree is a binary tree in which for each node x in the tree, elements in the left subtree are less than info(x) and elements in the right subtree are greater than or equal to info(x). Various operations performed—

• Insertion • Searching • Deleting

32

Binary Search Tree 45 35

64

25

40 28

32

56 47

89 59

33

Insertion 140 100 50

200

25

90 80

150 140

300 180

34

Function to insert an item NODE insert(int item, NODE root){ NODE temp,cur,prev; temp = get_node(); /*Obtain a new node*/ temp->info = item; temp->llink = NULL; temp->rlink = NULL; if(root == NULL) return temp; prev = NULL; /*find the appropriate position*/ cur = root; while(cur != NULL) { prev = cur;/*Obtain parent and left or right child*/ cur = (item < cur->info) ? Cur->llink :cur->rlink; } if(item < prev->info) /*new node is less than parent */ prev->llink = temp; /*Insert towards left */ else prev->rlink = temp; /*Insert towards right */ return root; /*Return the root*/ }

35

Function to search for an item NODE search(int item,NODE root) { /* Search for the item */ while(root!=NULL && item!=root->info) { root=(iteminfo)? root->llink:root->rlink; } return root; } 36

Deletion • When we delete a node, we need to consider how we take care of the children of the deleted node. – This has to be done such that the property of the search tree is maintained.

37

Deletion Two cases: (1) the node is a leaf – Delete it immediately

(2) the node has one child – Adjust a pointer from the parent to bypass that node

38

Threaded Binary Tree Inorder traversal of a threaded binary tree – By using threads we can perform an inorder traversal without making use of a stack (simplifying the task) – Now, we can follow the thread of any node, ptr, to the “next” node of inorder traversal  If ptr->right_thread = TRUE, the inorder successor of ptr is ptr->right_child by definition of the threads  Otherwise we obtain the inorder successor of ptr by following a path of left-child links from the right-child of ptr until we reach a node with left_thread = TRUE 39

Summary • A directed tree is an acyclic graph, which has only one node with indegree 0 (root) and all other nodes have indegree 1. • A node that has an outdegree of 0, is called a Leaf node or Terminal node. • A tree in which outdegree of each node is less than or equal to two is called a Binary tree. • If the outdegree of every node is either 0 or 2, it is called Strictly Binary Tree. 40

Thank You!

41