3-1 trees and binary trees.pptnd binaryf

Introduction • Till now, we focussed only on linear data structures such as stacks, queues and linked lists. • But, in real-world situations, data relationships are not always linear. • Tree is one such non-linear data structure which stores the data elements in a hierarchical manner • . Each node of the tree stores a data value, and is linked to other nodes in a hierarchical fashion. • We will learn about the different types of trees and their related operations. • Most importantly, we will focus on binary tree and its variants, which are widely used in the field of computer science.

Basic Concept • A tree is defined as a finite set of elements or nodes, such that 1. One of the nodes present at the top of the tree is marked as root node. 2. The remaining elements are partitioned across multiple subtrees present below the root node. • T is a simple tree containing ten nodes with A being the root node. • The node A contains two subtrees. • The left subtree starts at node B while the right subtree starts at node C. • Both the subtrees further contain subtrees below them, thus indicating recursive nature of the tree data structure. • Each node in the tree has zero or more child nodes.

Tree Terminology Key Term Description Example (Tree T) Node It is the data element of a tree. Apart from storing a value, it also specifies links to the other nodes. A, B, C, D Root It is the top node in a tree A Parent A node that has one or more child nodes present below it is referred as parent node. B is the parent node of D and E Child All nodes in a tree except the root node are child nodes of their immediate predecessor nodes. H, I and J are child nodes of E Leaf It is the terminal node that does not have any child nodes. G, H, I, J and F are leaf nodes Internal node All nodes except root and leaf nodes are referred as internal nodes. B, C, D and E are internal nodes Sibling All the child nodes of a parent node are referred as siblings. D and E are siblings Degree The degree of a node is the number of subtrees coming out of the node. Degree of A is 2 Degree of E is 3

Tree Terminology contd… Key Term Description Example (Tree T) Level All the tree nodes are present at different levels. Root node is at level 0, its child nodes are at level 1, and so on. A is at level 0 B and C are at level 1 G, H, I, J are at level 3 Depth or Height It is the maximum level of a node in the tree. Depth of tree T is 3 Path It is the sequence of nodes from source node till destination node. A–B–E–J

Binary Tree • Binary tree is one of the most widely used non- linear data structures in the field of computer science. • It is a restricted form of a general tree. • The restriction that it applies to a general tree is that its nodes can have a maximum degree of 2. • That means, the nodes of a binary tree can have zero, one or two child nodes but not more than that. • As shown in the above binary tree, all nodes have a maximum degree of 2. • The maximum number of nodes that can be present at level n is 2n .

Strictly Binary Tree • A binary tree is called strictly binary if all its nodes barring the leaf nodes contain two child nodes.

Complete Binary Tree • A binary tree of depth d is called complete binary tree if all its levels from 0 to d–1 contain maximum possible number of nodes and all the leaf nodes present at level d are placed towards the left side. • A complete binary tree of level l will have maximum 2l nodes at each level, where l starts from 0. • Any binary tree with n nodes will have at the most n+1 null branches. • The total number of edges in a complete binary tree with n terminal nodes are 2(n-1). t level d are placed towards the left side.

Perfect Binary Tree • A binary tree is called perfect binary tree if all its leaf nodes are at the lowest level and all the non- leaf nodes contain two child nodes.

Balanced Binary Tree • A binary tree is called balanced binary tree if the depths of the subtrees of all its nodes do not differ by more than 1.

Left Skewed Balanced Binary Tree • If the right sub-tree is missing in every node of a tree we call it as left skewed tree.

Right Skewed Balanced Binary Tree • If the left sub-tree is missing in every node of a tree we call it is right sub-tree.

Binary Tree Representation •The sequential representation of binary trees is done by using arrays •The linked representation is done by using linked lists.

Array Representation •One-dimensional array is used for storing the node elements. •The following rules are applied while storing the node elements in the array: 1.The root node is stored at the first position in the array while its left and right child nodes are stored at the successive positions. 2.If a node is stored at index location i then its left child node will be stored at location 2i+1 while the right child node will be stored at location 2i+2.

Example binary tree • T1 is a binary tree containing seven nodes with A being the root node. • B and C are the left and right child nodes of A respectively. • Let us apply the rules explained earlier to arrive at the array representation of binary tree T1 .

Array representation binary tree T1 • the array index values for each of the tree nodes. • Array A is used for storing the node values.

Array representation binary tree T1 contd.. • modify the binary tree T 1 a little by deleting nodes E and F.

Array Representation advantage •The only advantage with this type of representation is that the direct access to any node can be possible and finding the parent or left children of any particular node is fast because of the random access.

Array Representation disadvantage •In this type of representation the maximum depth of the tree has to be fixed Because we have decide the array size. •If we choose the array size quite larger than the depth of the tree, then it will be wastage of the memory. And if we choose array size lesser than the depth of the tree then we will be unable to represent some part of the tree. •The insertions and deletion of any node in the tree will be costlier as other nodes has to be adjusted at appropriate positions so that the meaning of binary tree can be preserved. •The major disadvantage with this type of representation is wastage of memory. •It efficiently utilizes the memory space only when the tree is a complete binary tree. Otherwise, there are always some memory locations lying vacant in the array.

Linked Representation of binary tree •To avoid the disadvantages associated with array representation, linked representation is used for implementing binary trees. •It uses a linked list for storing the node elements. •Each tree node is represented with the help of the linked list node comprising of the following fields: 1.INFO Stores the value of the tree node. 2.LEFT Stores a pointer to the left child. 3.RIGHT Stores a pointer to the right child. •In addition, there is a special pointer that points at the root node.

Linked list representation of binary tree contd.. • Below figure shows how linked list is used for representing a binary tree in memory

Linked Representation of binary tree contd.. •The linked representation of binary tree uses dynamic memory allocation technique for adding new nodes to the tree. •It reserves only that much amount of memory space as is required for storing its node values. •Thus, linked representation is more efficient as compared to array representation.

Linked Representation of binary tree advantages •This representation is superior to our array representation as there is no wastage of memory. •There is no need to have prior knowledge of depth of the tree. •Using dynamic memory concept one can create as much memory(nodes) as required. •By chance if some nodes are unutilized one can delete the nodes by making the address free. •Insertions and deletions which are the most common operations can be done without moving the nodes.

Linked Representation of binary tree disadvantages •This representation does not provide direct access to a node and special algorithms are required. • This representation needs additional space in each node for storing the left and right subtrees.

Binary Tree Traversal •Traversal is the process of visiting the various elements of a data structure. •Binary tree traversal can be performed using three methods: 1.Preorder 2.Inorder 3.Postorder

Binary Tree Preorder Traversal • The preorder traversal method operations: a) Process the root node (N). b) Traverse the left subtree of N (L). c) Traverse the right subtree of N (R). •A-B-C-D-E data at the root node will be printed first then we move on the left sub-tree and go on printing the data till we reach to the left most node. •Print the data at that node and then move to the right sub- tree. •Follow the same principle at each sub-tree and go on printing the data accordingly.

Binary Tree Inorder tranersal • The inorder traversal method operations: a) Traverse the left subtree of N (L). b) Process the root node (N). c) Traverse the right subtree of N (R). C-B-A-D-E is the inorder traversal i.e. first we go towards the leftmost node. i.e. C so print that node C. Then go back to the node B and print B. Then root node A then move towards the right sub-tree print D and finally E.

Binary Tree Post order traversal • traversal method operations: a) Traverse the left subtree of N (L). b) Traverse the right subtree of N (R). c) Process the root node (N). •postorder traversal is C-D-B-E-A. •Left|Right|Root principle i.e. move to the leftmost node, if right sub-tree is there or not if not then print the leftmost node, if right sub-tree is there move towards the right most node. The key idea here is that at each sub-tree we are following the Left| Right|Root principle and print the data accordingly.

Binary Tree Traversal contd… • Preorder traversal sequence A–B–D–E–G–C–F • Inorder traversal sequence D–B–G–E–A–C–F • Postorder traversal sequence D–G–E–B–F–C–A

Binary Tree Traversal contd… • The pre-order traversal is: A-B-D-E-H-C-F-G-I-K-J • The in-order traversal is : D-B-H-E-A-F-C-K-I-G-J • The post-order traversal is:D-H-E-B-F-K-I-J-G-C-A

3-1 trees and binary trees.pptnd binaryf

More Related Content

Similar to 3-1 trees and binary trees.pptnd binaryf

Recently uploaded

3-1 trees and binary trees.pptnd binaryf