- 作业标题：CSCI 2110 - Data Structures and Algorithms - lab 7
- 课程名称：Dalhouse University CSCI 2110 Data Structures and Algorithms
- 完成周期：2天
描述
The objective of this lab is to help you get familiar with the binary tree data structure. Download the
example code/files provided along with this lab document. You will need the following files to complete
your work:
BinaryTree.java (Generic BinaryTree Class)
BinaryTreeDemo.java (A class demonstrating the methods of the BinaryTree class)
Marking Scheme
Each exercise carries 10 points.
Working code, Outputs included, Efficient, Good basic comments included: 10/10
No comments or poor commenting: subtract one point
Unnecessarily inefficient: subtract one point
No outputs and/or not all test cases covered: subtract up to two points
Code not working : subtract up to six points depending upon how many methods are incorrect. TAs can
and will test cases beyond those shown in sample inputs.
Your final score will be scaled down to a value out of 10. For example, if there are three exercises and
you score 9/10, 10/10 and 8/10 on the three exercises, your total is 27/30 or 9/10.
Error checking: Unless otherwise specified, you may assume that a user enters the correct data types
and the correct number of input entries, that is, you need not check for errors on input.
Submission: All submissions are through Brightspace. Deadline for submission: Sunday, November 7th,
2021, 11.59 PM
What to submit:
Submit one ZIP file containing all source code (files with .java suffixes) and text documents containing
sample outputs for all the exercises.
You MUST SUBMIT .java files that are readable by your TAs. If you submit files that are unreadable such
as .class, you will lose points. Please additionally comment out package specifiers.
Late Submission Penalty: The lab is due on Sunday at 11.59 PM. Late submissions up to 5 hours
(4.59 AM on Monday) will be accepted without penalty. After that, there will be a 10% late penalty
per day on the mark obtained. For example, if you submit the lab on Monday at 12 noon and your
score is 8/10, it will be reduced to 7.2/10. Submissions past two days (48 hours) after the grace
submission time, that is, submission past 4.59 AM Wednesday will not be accepted.
。。。
Exercise 1 (Binary Tree Methods)
For this exercise, you will complete a number of methods in the BinaryTree.java file.
- Complete the recursive method called nodes in the BinaryTree.java file. This method should return
the number of nodes in a binary tree.
To determine the number of nodes in a binary tree you can apply the following rules:
• if the binary tree is empty, then the number of nodes is zero.
• otherwise, the number of nodes is equal to one plus number of nodes in the left subtree plus
number of nodes in the right subtree.
- Complete the recursive method called height in the BinaryTree.java file. This method should return
the height of a binary tree.
To determine the height of a binary tree you can apply the following rules:
• if the binary tree is empty, then the height of the binary tree is -1.
• otherwise, the height is equal to 1 plus the height of either the left subtree or the right subtree,
whichever is greater.
- Complete the recursive isBalanced method in the BinaryTree.java file. This method should return a
Boolean reflecting whether or not a binary tree is height balanced.
A binary tree is height balanced if, for every node in the tree, the height of its left subtree differs from the
height of its right subtree by no more than one. In other words, either the left and the right subtrees are of
the same height, or the left is one higher than the right, or the right is one higher than the left.
- Complete the levelorder method in the BinaryTree.java file. This static, dynamic method should
perform a level order traversal of a binary tree passed to it as an argument. To accomplish this, you
will implement a simple breadth first search. You can use an ArrayList of type BinaryTree as your
agenda, adding your root node before iterating. Traverse the tree by removing the first element from
the agenda, printing, and adding the children of the node removed to the agenda. Repeat until your
agenda is empty
。。。
