ICT 107 - Data Structures and Algorithms Unit 3 PDF

ICT 107 – Data Structures and Algorithms Unit 3: Lists and Recursion Lists In a linked list, each data item is embedded in a link. A link is an object of a class called something like Link. Because there are many similar links in a list, it makes sense to...

ICT 107 – Data Structures and Algorithms Unit 3: Lists and Recursion Lists In a linked list, each data item is embedded in a link. A link is an object of a class called something like Link. Because there are many similar links in a list, it makes sense to use a separate class for them, distinct from the linked list itself. Each Link object contains a reference (usually called next) to the next link in the list. A field in the list itself contains a reference to the first link. This relationship is shown in figure below. Elements in linked lists are not stored in sequence. Instead, they are scattered and connected through links (Prev and Next). Here we have 3 elements in a linked list. Dog - it is the first element that holds null as previous address and the address of Cat as the next address Cat - it is the second element that holds an address of Dog as the previous address and the address of Cow as the next address Cow - it is the last element that holds the address of Cat as the previous address and null as the next element Page 1 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms Most Common List A Simple Linked List Simple linked list only allows operations like: Inserting an item at the beginning of the list Deleting the item at the beginning of the list Iterating through the list to display its contents Double-Ended Lists A double-ended list is similar to an ordinary linked list, but it has one additional feature: a reference to the last link as well as to the first. Circular Lists A circular list is a linked list in which the last link points back to the first link. There are many ways to design a circular list. Sometimes there is a pointer to the “start” of the list. However, this makes the list less like a real circle and more like an ordinary list that has its end attached to its beginning. Linked Lists Methods addFirst() - Adds an item to the beginning of the list. Implementation in Java import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList cars = new LinkedList(); cars.add("Volvo"); cars.add("BMW"); cars.add("Ford"); Page 2 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms // Use addFirst() to add the item to the beginning cars.addFirst("Mazda"); System.out.println(cars); } } Output: [Mazda, Volvo, BMW, Ford] addLast() - Add an item to the end of the list Implementation in Java import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList cars = new LinkedList(); cars.add("Volvo"); cars.add("BMW"); cars.add("Ford"); // Use addLast() to add the item to the end cars.addLast("Mazda"); System.out.println(cars); } } Output: [Volvo, BMW, Ford, Mazda] removeFirst() - Remove an item from the beginning of the list. Implementation in Java import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList cars = new LinkedList(); cars.add("Volvo"); cars.add("BMW"); cars.add("Ford"); cars.add("Mazda"); // Use removeFirst() remove the first item from the list cars.removeFirst(); System.out.println(cars); Page 3 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms } } Output: [BMW, Ford, Mazda] removeLast() - Remove an item from the end of the list. Implementation in Java import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList cars = new LinkedList(); cars.add("Volvo"); cars.add("BMW"); cars.add("Ford"); cars.add("Mazda"); // Use removeLast() remove the last item from the list cars.removeLast(); System.out.println(cars); } } Output: [Volvo, BMW, Ford] getFirst() - Get the item at the beginning of the list. Implementation in Java import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList cars = new LinkedList(); cars.add("Volvo"); cars.add("BMW"); cars.add("Ford"); cars.add("Mazda"); // Use getFirst() to display the first item in the list System.out.println(cars.getFirst()); } } Output: Volvo Page 4 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms getLast() - Get the item at the end of the list. Implementation in Java import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList cars = new LinkedList(); cars.add("Volvo"); cars.add("BMW"); cars.add("Ford"); cars.add("Mazda"); // Use getLast() to display the last item in the list System.out.println(cars.getLast()); } } Output: Mazda Recursion Recursion is the process of defining a problem (or solution to a problem) in terms of a simpler version of itself. For example, we can define the operation “Find your way home” as: 1. If you are at home, stop moving. 2. Take one step toward home. 3. “Find your way home” Here are the solutions in finding your way home is two steps (three steps). First, we don’t go home if we are already home. Second, we do a very simple action that makes your situation simpler to solve. Finally, we redo the entire algorithm. Parts of a Recursion Algorithm 1. Base Case (i.e., when to stop) – The base case is the solution to the “simplest” possible problem. 2. Work toward Base Case – The work toward the base case is where we make the problem simpler. 3. Recursive Call (i.e., call ourselves) – The recursive call, is where we use the same algorithm to solve a simpler version of the problem. Most Common Recursion Linear Recursion Page 5 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms A linear recursion is a function that only makes single call to itself each time the function runs. The factorial function is a good example of linear recursion. Tail Recursive A form of linear recursion. In a tail recursion, the recursive call is the last thing to the function does. Often, the value of the recursive call is returned. As such, tail recursive functions can often be easily implemented in an iterative manner; by taking out the recursive call and replacing it with loop, the same effect can generally be achieved. Binary Recursion Some recursive functions don’t just have one call to themselves, they have two. Functions with two recursive calls are referred to as binary recursive functions. The mathematical combinations operation is a good example of a function that can quickly be implemented as a binary recursive function. Page 6 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms Implementation in Java public class Main { public static void main(String[] args) { int result = sum(10); System.out.println(result); } public static int sum(int k) { if (k > 0) { return k + sum(k - 1); } else { return 0; } } } Output: 55 Example Explained When the sum() function is called, it adds parameter k to the sum of all numbers smaller than k and returns the result. When k becomes 0, the function just returns 0. When running, the program follows these steps: 10 + sum(9) 10 + ( 9 + sum(8) ) 10 + ( 9 + ( 8 + sum(7) ) )... 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0) 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 Since the function does not call itself when k is 0, the program stops there and returns the result. Halting Just as loops can run into the problem of infinite looping, recursive functions can run into the problem of infinite recursion. Infinite recursion is when the function never stops calling itself. Every recursive function should have a halting condition, which is the condition where the function stops calling itself. Implementation in Java public class Main { public static void main(String[] args) { int result = sum(5, 10); Page 7 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.  ICT 107 – Data Structures and Algorithms System.out.println(result); } public static int sum(int start, int end) { if (end > start) { return end + sum(start, end - 1); } else { return end; } } } Output: 45 Page 8 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms Unit 4: Trees What Is a Tree? We’ll be mostly interested in a particular kind of tree called a binary tree, but let’s start by discussing trees in general before moving on to the specifics of binary trees. A tree consists of nodes connected by edges. In such a picture of a tree the nodes are represented as circles, and the as lines connecting the circles. A general (non-binary) tree Why Use Binary Trees? Why might you want to use a tree? Usually, because it combines the advantages of two other structures: an ordered array and a linked list. You can search a tree quickly, as you can an ordered array, and you can also insert and delete items quickly, as you can with a linked list. Let’s explore these topics a bit before delving into the details of trees. Tree Terminology Many terms are used to describe particular aspects of trees. You need to know a few of them so our discussion will be comprehensible. Fortunately, most of these terms are related to real-world trees or to family relationships (as in parents and children), so they’re not hard to remember. Page 1 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms Path Think of someone walking from node to node along the edges that connect them. The resulting sequence of nodes is called a path. Root The node at the top of the tree is called the root. There is only one root in a tree. For a collection of nodes and edges to be defined as a tree, there must be one (and only one!) path from the root to any other node. Parent Any node (except the root) has exactly one edge running upward to another node. The node above it is called the parent of the node. Child Any node may have one or more lines running downward to other nodes. These nodes below a given node are called its children. Leaf A node that has no children is called a leaf node or simply a leaf. There can be only one root in a tree, but there can be many leaves. Sub tree Any node may be considered to be the root of a sub tree, which consists of its children, and its children’s children, and so on. If you think in terms of families, a node’s sub tree contains all its descendants. Visiting A node is visited when program control arrives at the node, usually for the purpose of carrying out some operation on the node, such as checking the value of one of its data fields or displaying it. Merely passing over a node on the path from one node to another is not considered to be visiting the node. Traversing To traverse a tree means to visit all the nodes in some specified order. For example, you might visit all the nodes in order of ascending key value. There are other ways to traverse a tree, as we’ll see later. Levels The level of a particular node refers to how many generations the node is from the root. If we assume the root is Level 0, then its children will be Level 1, its grandchildren will be Level 2, and so on. Page 2 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms Keys We’ve seen that one data field in an object is usually designated a key value. This value is used to search for the item or perform other operations on it. In tree diagrams, when a circle represents a node holding a data item, the key value of the item is typically shown in the circle. Binary Trees If every node in a tree can have at most two children, the tree is called a binary tree. The two children of each node in a binary tree are called the left child and the right child, corresponding to their positions when you draw a picture of a tree. A node in a binary tree doesn’t necessarily have the maximum of two children; it may have only a left child, or only a right child, or it can have no children at all (in which case it’s a leaf). Unbalanced Trees Notice that some of the trees you generate are unbalanced; that is, they have most of their nodes on one side of the root or the other. Individual sub trees may also be unbalanced. Page 3 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms Finding a Node Finding a node with a specific key is the simplest of the major tree operations. Remember that the nodes in a binary search tree correspond to objects containing information. They could be person objects, with an employee number as the key and also perhaps name, address, telephone number, salary, and other fields. Or they could represent car parts, with a part number as the key value and fields for quantity on hand, price, and so on. However, the only characteristics of each node that we can see in the Workshop applet are a number and a color. A node is created with these two characteristics, and keeps them throughout its life. Now let’s find the node representing the item with key value 57. Traversing the Tree Page 4 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms Traversing a tree means visiting each node in a specified order. This process is not as commonly used as finding, inserting, and deleting nodes. One reason for this is that traversal is not particularly fast. But traversing a tree is useful in some circumstances, and it’s theoretically interesting. There are three simple ways to traverse a tree. They’re called preorder, inorder, and postorder. The order most commonly used for binary search trees is inorder, so let’s look at that first and then return briefly to the other two. Inorder Traversal An inorder traversal of a binary search tree will cause all the nodes to be visited in ascending order, based on their key values. If you want to create a sorted list of the data in a binary tree, this is one way to do it. The simplest way to carry out a traversal is the use of recursion. A recursive method to traverse the entire tree is called with a node as an argument. Initially, this node is the root. The method needs to do only three things: 1. Call itself to traverse the node’s left subtree. 2. Visit the node. 3. Call itself to traverse the node’s right subtree. Implementation in Java // Tree traversal in Java class Node { int item; Node left, right; public Node(int key) { item = key; left = right = null; } } class BinaryTree { // Root of Binary Tree Node root; BinaryTree() { root = null; } void inorder(Node node) { if (node == null) return; // Traverse left inorder(node.left); // Traverse root Page 5 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms System.out.print(node.item + "->"); // Traverse right inorder(node.right); } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); } } Output: Inorder traversal 5->12->6->1->9-> Preorder and Postorder Traversals You can traverse the tree in two ways besides inorder; they’re called preorder and postorder. It’s fairly clear why you might want to traverse a tree inorder, but the motivation for preorder and postorder traversals is more obscure. However, these traversals are indeed useful if you’re writing programs that parse or analyze algebraic expressions. Let’s see why that should be true. What does all this have to do with preorder and postorder traversals? Let’s see what’s involved. For these other traversals the same three steps are used as for inorder, but in a different sequence. Here’s the sequence for a preorder() method: 1. Visit the node. 2. Call itself to traverse the node’s left subtree. 3. Call itself to traverse the node’s right subtree. Implementation in Java // Tree traversal in Java class Node { int item; Node left, right; public Node(int key) { item = key; left = right = null; } Page 6 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms } class BinaryTree { // Root of Binary Tree Node root; BinaryTree() { root = null; } void preorder(Node node) { if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("\nPreorder traversal "); tree.preorder(tree.root); } } Output: Preorder traversal 1->12->5->6->9-> The third kind of traversal, postorder, contains the three steps arranged in yet another way: 1. Call itself to traverse the node’s left subtree. 2. Call itself to traverse the node’s right subtree. 3. Visit the node. Implementation in Java // Tree traversal in Java Page 7 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited. ICT 107 – Data Structures and Algorithms class Node { int item; Node left, right; public Node(int key) { item = key; left = right = null; } } class BinaryTree { // Root of Binary Tree Node root; BinaryTree() { root = null; } void postorder(Node node) { if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("\nPostorder traversal"); tree.postorder(tree.root); } } Output: Postorder traversal 5->6->12->9->1-> Page 8 of 8 Prepared by: Stennaley S. Rupero ***Disclaimer: This module is owned by ISAT University. Unauthorized reproduction or distribution without the consent of the university and the module writer is strictly prohibited.