BINARY OTHER TREES - 1

Slide 1: 

UNIT - III CHAPTER – 12 BINARY OTHER TREES

CONTENTS : 

CONTENTS 1. TREES 2. BINARY TREES 3. ADT OF BINARY TREE 4. PROPERTIES OF BINARY TREES 5. REPRESENTATION OF BINARY TREES 5.1.ARRAY REPRESENTATION 5.2.LINKED REPRESENTATION 6. COMMON BINARY TREE OPERATIONS 7. BINARY TREE TRAVERSAL 8. THE CLASS LINKED BINARY TREE 9. APPLICATIONS

Slide 3: 

Trees

Slide 4: 

Nature Lover’s View Of A Tree

Slide 5: 

Computer Scientist’s View

1. TREES : 

1. TREES Definition-1 A tree is a finite non-empty set of elements. One of these elements is called the “Root”. And the remaining elements are partitioned into trees, which are called the sub trees of ‘t’ A H B E C G F D I Sub-tree Sub-tree

1. TREES : 

1. TREES Definition-2 A tree consist of a finite set of elements, called nodes and a finite set of directed lines, called branches, that connect the nodes. 1. A tree consist of a finite set of elements, called ‘nodes’. 2. And a finite set of directed lines, called ‘branches’. That connect the nodes. 3. the number of branches associated with a node is the degree of the node. (i) when the branches is directed toward the node, it’s an “in-degree”.

Slide 8: 

(ii) when the branch is directed way from the nodes, it’s an “out-degree” branch. (iii) The sum of the in-degree and out-degree braches is the degree of the node. If the tree is not empty, then the first node is called “Root”. In addition to root, many different terms are used to describe the attributes of a tree. i) Leaf : any node with out-degree of zero (or) nodes with no sub-tree (or) children ii) Internal Node: a node that’s not a root (or) a leaf iii) parent: if it has a successor node (or) it has an out-degree greater than zero. iv) child: a node with a predecessor is called child v) siblings: tow (or) more nodes with same parent are called siblings.

Slide 9: 

A H B E C G F D I Parents : A, B, F Leaves : C, D, E, G, H, I Children : B, E, F, C, D, G, H, I Internal nodes : B, F Siblings : {B, E, F}, {C,D}, {G, H, I} Level-3 Level-2 Level-1

Slide 10: 

Some texts start level numbers at 1 rather than at 0. Root is at level 1. Its children are at level 2. The grand children of the root are at level 3. We shall number levels with the root at level 1. Height = Depth of Tree: The level of a node is its distance from the root. The height of a tree is the level of the leaf in the longest path from the root

Slide 11: 

A H B E C G F D I Level-3 Level-2 Level-1 The Height = Depth of the tree is ‘ 3’

Slide 12: 

12 Levels and Height Root is at level 1 and its children are at level 2. Height = depth = number of levels

Slide 13: 

13 Tree Terminology (or) Hierarchical data & Tree The element at the top of the hierarchy is the root. Elements next in the hierarchy are the children of the root. Elements next in the hierarchy are the grandchildren of the root, and so on. Elements at the lowest level of the hierarchy are the leaves.

Slide 14: 

Java’s Classes

Slide 15: 

15 Other Definitions Leaves, Parent, Grandparent, Siblings,Ancestors, Descendents Leaves = {Mike,AI,Sue,Chris} Parent(Mary) = Joe Grandparent(Sue) = Mary Siblings(Mary) = {Ann,John} Ancestors(Mike) = {Ann,Joe} Descendents(Mary)={Mark,Sue}

Slide 16: 

Node Degree = Number Of Children 3 2 1 1 0 0 1 0 0

Slide 17: 

Tree Degree = Max Node Degree Degree of tree = 3.

2. BINARY TREES : 

2. BINARY TREES Definition A binary tree ‘T’ is a finite collection of elements when the binary tree is not empty, it has a root element and the remaining elements are partitioned into two binary trees, which are called the left and right sub-tree of ‘T’. Difference between TREE & BINARY TREE Binary Tree Tree (i) Each element in the Each element in the tree has binary tree has exactly exactly any no. of elements. two elements. (or) (or) No node in a binary tree there is no limit on the may have a degree more degree of a node in a tree. than ‘ 2 ‘.

Slide 19: 

(ii) A binary tree may A tree can’t be empty. empty. (iii) Sub-tree of each element sub-tree of each element in a binary tree are ordered in a tree are un-ordered. (iv) binary tree & tree are different when viewed as “binary tree”. (v) binary tree & tree are same when viewed as “ tree”.

3. ADT OF BINARY TREE : 

3. ADT OF BINARY TREE Abstract DataType Binary Tree { instances: collection of elements; if not empty, the collection is partitioned into a root, left subtree, and right subtree; each subtree is also a binary tree; operations is Empty : return true if empty, return false otherwise root() : return the root element; return null if the tree is empty; makeTree(root, left, right) : create a binary tree with root as the root element, left(right) as the left(right) subtree removeLeftSubtree(): remove the left subtree and return it;

Slide 21: 

remove RightSubtree(): remove the right subtree and return it preOrder : preorder traversal of binary tree inOrder : inorder traversal of binary tree postOrder: postorder traversal of binary tree levelOrder : level-order traversal of binary tree }

4. PROPERTIES OF BINARY TREES : 

4. PROPERTIES OF BINARY TREES Property-1 The drawing of every binary tree with ‘ n ‘ elements n > 0, has exactly n-1 edges. Proof: every element in a binary tree (Except the root) has exactly one parent. There is exactly one edge between each child and its parent. So, the no. of edges is n-1. (e.g) Let us assume n=3 elements (A,B,C) the no. of edges are n-1 (3-1) = 2edges. A C B edge edge

Slide 23: 

Property-2 A binary tree of height (h), h>=0 has at least ‘h’ and at most 2h-1 elements in it. Proof: since each level has at least one element at each level. The no. of element is at least ‘h’. As each element can have at most two children, th no. of elements at level – I is at most 2i-1, i>0. For h=0, the total no. of elements is 0, which is equal to 20-1. For h>0, the no. of elements can’t exceed. ∑n 2 i – 1 = 2h – 1 i=1 A C B Level-1 Level-2

Slide 24: 

the no. of elements = 3 the level (or) height of the tree (h) = 2 (i.e) The no. of elements in the tree = 2h – 1 = 22 – 1 = 4 – 1 = 3 the no. of elements in the above figure is ‘3’ Property-3 The height of a binary tree that contains ‘n’, n>=0 elements is at most ‘n’ and at least [log 2 (n+1)] Proof: Since there must be at least one elements at each levels, the height can’t exceed ‘n’. From property-2 we know that a binary tree of height (h) can have no more than 2h-1 elements. So n<=2h-1. Hence h>= log 2 (n+1)]. Since ‘h’ is an integer we get h >= log 2 (n+1)]

FULL BINARY TREE & COMPLETE BINARY TREE : 

FULL BINARY TREE & COMPLETE BINARY TREE FULL BINARY TREE A full binary tree of height h has exactly 2h-1 nodes. Numbering the nodes in a full binary tree Number the nodes 1 through 2h-1 Number by levels from top to bottom Within a level, number from left to right Full Binary Tree of Height - 4 Level-1 Level-2 Level-3 Level-4

Slide 27: 

(i.e) h = 4; 2h-1 24-1= 16-1 = 15-elements COMPLETE BINARY TREE suppose we delete k-elements numbered 2h-1, the resulting binary tree is called ‘complete binary tree”. Level-1 Level-2 Level-3 Level-4

Slide 28: 

Suppose we want to delete the elements in the ‘level-3’, then use the following formula: 2h-i The level/height to be deleted (h) = 3 The no. of elements in the level-(3) (i) = 4 2h-i = 23-4 = 8 – 4 = 4 (i.e) The above figure is redraw as follow: 1 3 2 4

Slide 29: 

In binary tree each element have at most two children, where as in complete binary tree any one of the node (or) element have only one child. 1 3 2 4 1 3 2 4 5 6 1 2 a b c Complete Binary Trees

Slide 30: 

Property-4 Let ‘i’ be the number assigned to an element of a complete binary tree. The following are Tree. (i) If i=1, then this element is the root of the binary tree. If i>1, then parent of this element has been assigned the numbr[i/2]. if ‘i’ = 3; 3 > 1; 3/2=1 the parent of element in node 3 is in 1. (ii) If 2i>n, then this element has no left child. Otherwise, it’s left child has been assigned the number 2i. where: n- no.of elements i – no. of elements in each level 1 3 2 4 5 6 1 2 4 3 6 5

Slide 31: 

(e.g) let us take the following figure from the figure the no.of elements = 6 Let us take level-(2) i = 2; n = 6 2i > n 2 * 2 > 6 4 > 6 at 4 th position the left element is (D), here the left child has been assigned the number 2i. A C B D D E 1 2 4 3 6 5

Slide 32: 

(iii) if 2i+1>n, then this element has no right child. Otherwise, it’s right child has been assigned the number 2i+1 (e.g) let us take level-(2); then i = 2; n=6 2i + 1 > n 2 * 2 +1 > 6 4+1 > 6 5 > 6 At 5 th position the right element is (E). Here, the right child has been assigned the number 2i+1.

5. REPRESENTATION OF BINARY TREES : 

5. REPRESENTATION OF BINARY TREES We can represent the Binary tree either by using arrays (or) linked list binary tree is a non-linear data structure. 5.1.ARRAY REPRESENTATION The binary tree is represented in an array by storing each element at the array position corresponding to the number assigned to it. 1 2 3 4 6 7 8 9

Slide 34: 

* INCOMPLETE BINARY TREE The array representation of a binary tree utilize property-4. The binary tree to be represented as a complete binary tree with some missing element is shown in the following figure.

Slide 35: 

The first binary tree has 3-elements (A,B,C), and the second binary tree has 5-elements (A,B,C,D,E). Un-shaded circles represents missing elements. In an array based representation the binary tree is represented in an array by storing each element at the array position corresponding to the no. assigned to it. Missing elements are represented by white boxes. This representation is quite wasteful of space when many elements are missing.

Right-Skewed Binary Tree : 

Right-Skewed Binary Tree A binary tree that has n-elements may require an array of size 2n-1 for it’s representation. This maximum size is needed when each element of the n-element binary tree is the right child of it’s parent. Binary tree of this type are called “Right Skewed” Binary tree.

Slide 37: 

Example: form the above figure the total no. of elements are ‘4’, the calculation of total no. of array size is as follow: if n = 4; 2n-1; 24-1= 16-1 = 15 The array representation of above figure is calculated as follow: (1) let us take node ‘A’ n = 1 2n-1; 21-1 = 2-1 = 1 the array position of node ‘A’ is 1 (2) let us take node ‘B’ n = 2 2n-1; 22-1 = 4-1 = 3 the array position of node ‘B’ is 3

Slide 38: 

(3) let us take node ‘C’ n = 3 2-1; 23-1 = 8-1 = 7 the array position of node ‘C’ is 7 (4) let us take node ‘D’ n = 4 2-1; 24-1 = 16-1 = 15 the array position of node ‘D’ is 15 Right-skewed binary tree wastes the most space

5.2.LINKED REPRESENTATION : 

5.2.LINKED REPRESENTATION The most popular way to present a binary tree is Linked representation. This representation uses Links (or) pointers to represent binary tree. Each element is represented by a node that has two link fields (leftChild and rightChild) plus an element (or) data field.

Slide 40: 

Each edge in the drawing of a binary tree is represented by a pointers from the “parent node” to the “child node”. This pointer is placed in the approximate link field of the parent node. Linked representation of Binary tree: A B C

Slide 41: 

A B C D E G H Left Right Pointer Pointer

6. COMMON BINARY TREE OPERATIONS : 

6. COMMON BINARY TREE OPERATIONS Some of the operations that are commonly performed on binary trees are as follow: (1) Determine the height (2) Determine the number of nodes. (3) Make a copy (4) Determine if two binary trees are identical (5) Display the binary tree (6) Delete a tree (7) If it is an expression tree, evaluate the expression (8) If it is an expression tree, obtain the parenthesized form of the expression These operation can be performed by traversing the binary tree in a systematic manner. In a binary tree traversal, each element is visited exactly once.

7. BINARY TREE TRAVERSAL : 

7. BINARY TREE TRAVERSAL There are Four ways to traverse a binary tree: Preorder The root of the subtree is processed first before going into the left then right subtree (root, left, right). Inorder After the complete processing of the left subtree the root is processed followed by the processing of the complete right subtree (left, root, right). Postorder The root is processed only after the complete processing of the left and right subtree (left, right, root). Level order The tree is processed by levels. So first all nodes on level i are processed from left to right before the first node of level i+1 is visited

Preorder : 

Preorder This traversal follow the following general strategies: Root – Left – Right 1. Visit the Root 2. Traverse the Left Sub-tree preorder 3. Travers the Right sub-tree preorder A B C Left sub-tree Right sub-tree Pre-order traversal of above tree is – A B C

Algorithm : 

Algorithm algorithm preorder Traverse a binary tree in Root-Left-Right sequence Precondition : root is the entry node of a tree (or) sub-tree Postcondition : each node has been processed in order 1. if (root is not null) 1. process (root) 2. preorder ( root  left subtree) 3. preorder ( root  right subtree) 2. end if 3. return end preorder

Algorithm (recursive procedure) : 

Algorithm (recursive procedure) Procedure PREORDER (T) Given a binary tree whose root node address is given by a pointer variable ‘T’. This algorithm traverse the tree in pre-order in a recursive manner. 1. [process the root node] if T = NULL then write (Data (T) ) else write (‘empty Tree ‘) return 2. [process of left subtree] if LPTR (T) = NULL then call preorder (LPTR (T) )

Slide 47: 

3. [process of right subtree] if RPTR (T) = NULL then call preorder (RPTR (T) ) 4. [finished] 5. Return

Slide 48: 

A B D C E G F A B C D E F G - + * A * B D C E - + A * B C * D E

Preorder Of Expression Tree : 

Preorder Of Expression Tree Gives prefix form of expression! / * + a b - c d + e f

INorder : 

INorder This traversal follow the following general strategies: Left -- Root -- Right 1. Traverse the Left Sub-tree in inorder 2. Visit the Root 3. Travers the Right sub-tree in inorder A B C Left sub-tree Right sub-tree Inorder traversal of above tree is – B A C

Algorithm : 

Algorithm algorithm inorder Traverse a binary tree in Left-Root-Right sequence Precondition : root is the entry node of a tree (or) sub-tree Postcondition : each node has been processed in order 1. if (root is not null) 1. inorder ( root  left subtree) 2.process (root) 3. inorder ( root  right subtree) 2. end if 3. return end inorder

Algorithm (recursive procedure) : 

Algorithm (recursive procedure) Procedure INORDER (T) Given a binary tree whose root node address is given by a pointer variable ‘T’. This procedure traverse the tree in inorder in a recursive manner. 1. [check for empty tree] if T = NULL then write (‘empty tree’) return 2. [process left subtree] if LPTR (T) = NULL then call postorder (LPTR (T) )

Slide 53: 

3. [process of root node] if T = NULL then write (data (T) ) 4. [process the right subtree] if RPTR (T) = NULL then call inorder(RPTR (T)) 5. [finished] 6. return

Slide 54: 

A B D C E G F C B A E F D G - + * A * B D C E A + B * C - D * E

postorder : 

postorder This traversal follow the following general strategies: Left -- Right -- Root 1. Traverse the Left Sub-tree in postorder 2. Travers the Right sub-tree in postorder 3. Visit the Root A B C Left sub-tree Right sub-tree Postorder traversal of above tree is –B C A

Algorithm : 

Algorithm algorithm postorder Traverse a binary tree in Left-Right-Root sequence Precondition : root is the entry node of a tree (or) sub-tree Postcondition : each node has been processed in order 1. if (root is not null) 1. postorder ( root  left subtree) 2. postorder ( root  right subtree) 3. process (root) 2. end if 3. return end postorder

Algorithm (recursive procedure) : 

Algorithm (recursive procedure) Procedure POSTORDER (T) Given a binary tree whose root node address is given by a pointer variable ‘T’. This procedure traverse the tree in postorder in a recursive manner. 1. [check for empty tree] if T = NULL then write (‘empty tree’) return 2. [process left subtree] if LPTR (T) != NULL then call inorder (LPTR (T) )

Slide 58: 

3. [process of right subtree] if RPTR (T) != NULL then call postorder (RPTR (T) ) 4. [process the root node] if T != NULL then write (Data (T) ) 5. [finished] 6. Return

Slide 59: 

A B D C E G F C B F E G D A - + * A * B D C E A B C * + D E * -

9. APPLICATIONS : 

9. APPLICATIONS 1. Placement of signal Boosters 2. Union – Find Problem