Tree & Graph Data Structures Notes PDF

 TREE & GRAPH DATA STRUCTURES MODULE IV Jacob P Cherian Asst.Professor Dept.of CSE, Saintgits College of Engineering...

 TREE & GRAPH DATA STRUCTURES MODULE IV Jacob P Cherian Asst.Professor Dept.of CSE, Saintgits College of Engineering 1 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  CONTENTS Introduction to Tree Data Structure Tree Operations Binary Tree Representations Tree Traversals Binary Search Trees Binary Search Tree Operations Introduction to Graph Data Structure Representation of Graphs Graph Traversal- BFS & DFS Application of Graphs 2 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Tree- Definition A tree is a finite set of one or more nodes such that: i)there is a specially designated node called the root. ii) remaining nodes are partitioned into n(n>0) disjoint sets T1,T2...Tn, where each Ti(i=1,2...n) are called subtrees of the root. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Trees- Basic Idea A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node. The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Example of a General Tree A ROOT NODE B C D E F G H I Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Terminology- Parent & Child A PARENT CHILDREN B C D E F G H I Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Terminology- Parent & Child A B C D E F PARENT G H I CHILDREN Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Trees- Basic Idea All Tree nodes are connected by links called edges. It’s an important part of trees, because it’s manages the relationship between nodes. Leaves are the last nodes on a tree. They are nodes without children. Like real trees, we have the root, branches, and finally the leaves. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Example of a General Tree A B C D E F LEAF NODES G H I Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Example of a General Tree A SIBLINGS B C D E F Nodes which have the same parent are called siblings G H I Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Terminology- Levels A LEVEL 0 B C LEVEL 1 D E F LEVEL 2 G H I LEVEL 3 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Terminology- Height of a Tree A B C The height of a tree is the number of edges on the longest downward path between the root and a leaf D E F Height = 3 G H I Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Binary Trees-Basic Idea A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Binary Tree- Example A Each node has either 0, 1 or 2 Children B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Size of a Binary Tree A Size = 8 The total number of nodes in a binary tree is known as the size of a binary tree B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering External Nodes & Internal Nodes A External node is a node with at least one child B C Internal node is a node with no children D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering External Nodes & Internal Nodes A External node is a node with at least one child B C Internal node is a node with no children D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Left Sub-tree & Right Sub-tree A Left Subtree of A B C Right Subtree of A D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Left Subtree & Right Subtree A B C Right Subtree of D E F Node C Left Subtree of Node C G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Maximum no:of nodes at any Level of a Binary Tree A Maximum no:of nodes possible at any level, (say i)of a binary tree 2i B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Full Binary Tree A full Binary tree is a special type of binary tree in which every parent node has either two or no children Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Full Binary Tree- Example Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Complete Binary Tree A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left. All the leaf elements must lean towards the left. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Complete Binary Tree- Example Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Identify- Binary Tree(BT), Complete BT or Full BT a) b) Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Identify- Binary Tree(BT), Complete BT or Full BT c) d) Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Identify- Binary Tree(BT), Complete BT or Full BT e) f) Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Tree Traversal Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Tree Traversal Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Inorder Traversal - (Left ST, N(Root), Right ST) LNR Preorder Traversal - (N(Root), Left ST, Right ST) NLR Postorder Traversal - (Left ST, Right ST, N(Root)) LRN Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal D G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DB G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBA G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBA G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBA G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBA G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAG G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAGE G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAGE G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAGEH G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAGEHC G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAGEHC G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Inorder Traversal LNR A B C D E F Inorder Traversal DBAGEHCF G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal A G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal AB G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal ABD G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal ABDC G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal ABDCE G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal ABDCEG G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal ABDCEGH G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Preorder Traversal NLR A B C D E F Preorder Traversal ABDCEGHF G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal D G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DB G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DB G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DB G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DB G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DBG G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DBG G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Postorder Traversal LRN A B C D E F Postorder Traversal DBGH G H Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering