Tree Abstract Data Type (ADT) PDF

Tree  OBJECTIVES Explain the Basic Principles of Tree ADT. Discuss the Types of Traversal. Discuss the Types of Tree.  Tree ADT A Tree Data Structure is an abstract model of a hierarchical structure. It is a non-linear data structure in which a collection of elements known as...

Tree  OBJECTIVES Explain the Basic Principles of Tree ADT. Discuss the Types of Traversal. Discuss the Types of Tree.  Tree ADT A Tree Data Structure is an abstract model of a hierarchical structure. It is a non-linear data structure in which a collection of elements known as nodes are connected to each other via edges such that there exists exactly one path between any two nodes.  Tree ADT In tree data structure, every individual element is called as nodes. Tree Terminologies  Tree Terminologies Node - A node is an entity that contains a key or value and pointers to its child nodes.  Tree Terminologies Root - It is the topmost node of a tree.  Tree Terminologies Edge – is the connecting link between any two nodes.  Tree Terminologies Parent Node – The node which is a predecessor of a node is called the parent node of that node.  Tree Terminologies Child Node – The node which is the immediate successor of a node is called the child node of that node.  Tree Terminologies Ancestors – any node in the path from the current node to the root node. Descendant – any node in the path from the current node to the leaf nodes.  Tree Terminologies Siblings - Children of the same parent node are called siblings.  Tree Terminologies Leaf Nodes – also called as External Nodes or Terminal nodes. The nodes which do not have any child nodes are called leaf nodes.  Tree Terminologies Internal Nodes – A node with at least one child.  Tree Terminologies Degree – the degree of a node is total number of children it has.  Tree Terminologies Level – The count of edges on the path from the root node to that node. The root node has level 0. The level is the distance from the root node.  Tree Terminologies Height – The height of a Tree is the height of the root node or the depth of the deepest node.  Tree Terminologies Depth – Depth of the root node is “0”  Tree Terminologies Path – The length of a Path is total number of edges in that path.  Tree Terminologies Subtree Each child node with a parent node forms a subtree recursively. Any connected structure below root is a subtree. Collection of subtrees makes a tree.  Tree Terminologies Forest - Is a set of disjoint trees. Tree Data Structure  Applications of Tree File System: This allows for efficient navigation and organization of files. Data Compression: Huffman coding is a popular technique for data compression that involves constructing a binary tree where the leaves represent characters and their frequency of occurrence. The resulting tree is used to encode the data in a way that minimizes the amount of storage required.  Applications of Tree Compiler Design: In compiler design, a syntax tree is used to represent the structure of a program. Database Indexing: B-trees and other tree structures are used in database indexing to efficiently search for and retrieve data. Classify The Two Traversals performed in tree adt A traversal of a Tree requires that each node of the tree be visited once. A typical reason to traverse a tree is to display the data stored at each node of the tree. LEVEL ORDER TRAVERSAL TYPES OF TRAVERSAL PREOREDER INORDER POSTORDER TRAVERSAL Starts at the root node and explores as deep as possible along each branch and backtrack to sibling branch until all nodes are visited. It is a recursive approach for all subtrees. PREORDER TRAVERSAL PROCESSING ORDER: Root ---→ Left ---→ Right Algorithm Visit the root Traverse the left subtree Travers the right subtree EXAMPLE PREORDER TRAVERSAL OUTPUT: ? PREORDER TRAVERSAL SHORTCUT INORDER TRAVERSAL PROCESSING ORDER: Left ---→ Root ---→ Right Algorithm Traverse the left subtree Visit the root Travers the right subtree EXAMPLE INORDER TRAVERSAL OUTPUT: ? INORDER TRAVERSAL SHORTCUT POSTORDER TRAVERSAL PROCESSING ORDER: Left ---→ Right ---→ Root Algorithm Traverse the left subtree Travers the right subtree Visit the root EXAMPLE POSTRDER TRAVERSAL OUTPUT: ? POSTORDER TRAVERSAL SHORTCUT PRACTICE ACTIVITY Find the Inorder Traversal. A B C D E F G H I J PRACTICE ACTIVITY A Find the preorder, postorder and B Inorder Traversal. C D E F G H I J K L PRACTICE ACTIVITY Visit the following tree in a breadth first manner and print all the nodes. REFERENCES: https://www.tutorialspoint.com/ https://www.geeksforgeeks.org https://www.programiz.com/ https://www.studysmarter.co.uk/ Thank you! Course Instructor: Engr. Laila A. Contreras Engr. Anthony G. Hernandez