{"id":403,"date":"2014-06-26T15:29:48","date_gmt":"2014-06-26T19:29:48","guid":{"rendered":"http:\/\/josephpcohen.com\/cs210-summer2014\/?p=403"},"modified":"2014-06-26T15:29:48","modified_gmt":"2014-06-26T19:29:48","slug":"hw5","status":"publish","type":"post","link":"https:\/\/josephpcohen.com\/teaching\/cs210\/hw5\/","title":{"rendered":"HW5 : Level-order Traversal"},"content":{"rendered":"<p>Due: Thursday 7\/3\/14 @5:30pm via users.cs.umb.edu:cs210\/hw5<\/p>\n<p><strong>Purpose:<\/strong>\u00a0To gain experience implementing a level order traversal of a binary tree.<\/p>\n<a href=\"http:\/\/josephpcohen.com\/teaching\/cs210-summer2014\/wp-content\/uploads\/sites\/2\/2014\/06\/Selection_031.png\"><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-408\" src=\"http:\/\/josephpcohen.com\/teaching\/cs210-summer2014\/wp-content\/uploads\/sites\/2\/2014\/06\/Selection_031.png\" alt=\"Selection_031\" width=\"500\" height=\"335\" srcset=\"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-content\/uploads\/sites\/2\/2014\/06\/Selection_031.png 898w, https:\/\/josephpcohen.com\/teaching\/cs210\/wp-content\/uploads\/sites\/2\/2014\/06\/Selection_031-300x201.png 300w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/a>\n<p>Study the following Level Order Traversal Algorithm so that you understand the design of the method that you will need to implement in this assignment.<\/p>\n<pre>Create a queue called nodes\nCreate an unordered list called results\nEnqueue a reference to the root node onto the nodes queue\nWhile the nodes queue is not empty\n    Dequeue the first element\n    If it is not null\n        add it to the rear of the results list\n        Enqueue the children of the element on the nodes queue\n    Else\n        Add null to the rear of the results list\nReturn an iterator for the results list\n<\/pre>\n<p>The following files are here: <a href=\"https:\/\/github.com\/ieee8023\/cs210-summer2014\" title=\"https:\/\/github.com\/ieee8023\/cs210-summer2014\" target=\"_blank\">https:\/\/github.com\/ieee8023\/cs210-summer2014<\/a> or <a href=\"http:\/\/josephpcohen.com\/cs210-summer2014\/wp-content\/uploads\/hw5.zip\">hw5<\/a><br \/>\nBinaryTreeADT.java : Interface for a binary tree.<br \/>\nBinaryTreeNode.java : Class used by LinkedBinaryTree for nodes of tree.<br \/>\nLinkedBinaryTree.java : Implements BinaryTreeADT interface.<br \/>\nLevelTraverse.java : Has a main method that builds a tree and iterates over it.<\/p>\n<p>You need to design and add code to the levelOrderIterator method of the LinkedBinaryTree class where indicated.<\/p>\n<p>1. Create a queue using the java.util.Queue interface and java.util.LinkedList class.<\/p>\n<p>2. Create a linkedlist using the java.util.LinkedList class to contain the elements in level order.<\/p>\n<p>3. Write code to implement the Level-order Traversal of the tree.<\/p>\n<p>4. Write a memo.txt describing any problems you had during this assignment and what you learned.<\/p>\n<p>A sample run of the finished program is shown here:<\/p>\n<pre>$ java LevelTraverse\nRoot\nChild1\nChild2\nGrandchild1\nGrandchild2\n. . .\n<\/pre>\n<p><strong>Grading (total 10 points):<\/strong><\/p>\n<p>Turn in the following files: BinaryTreeADT.java, BinaryTreeNode.java, LinkedBinaryTree.java, LevelTraverse.java, memo.txt<\/p>\n<p>3 points: Queue correctly filled<\/p>\n<p>5 points: Level order implemented correctly<\/p>\n<p>2 points: memo.txt, easy to grade.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Due: Thursday 7\/3\/14 @5:30pm via users.cs.umb.edu:cs210\/hw5 Purpose:\u00a0To gain experience implementing a level order traversal of a binary tree. Study the following Level Order Traversal Algorithm so that you understand the design of the method that you will need to implement in this assignment. Create a queue called nodes Create an unordered list called results Enqueue&#8230;  <a href=\"https:\/\/josephpcohen.com\/teaching\/cs210\/hw5\/\" class=\"more-link\" title=\"Read HW5 : Level-order Traversal\">Read more &raquo;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,1],"tags":[],"_links":{"self":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/posts\/403"}],"collection":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/comments?post=403"}],"version-history":[{"count":0,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/posts\/403\/revisions"}],"wp:attachment":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/media?parent=403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/categories?post=403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/tags?post=403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}