cs61b_lab11's Introduction
CS 61B Lab 11 April 10-11, 2014 Please make sure you have a partner for this lab. Copy the Lab 11 directory by doing the following, starting from your home directory. cp -r ~cs61b/lab/lab11 . All the code is in the dict package. You can compile it from your lab11 directory with javac -g dict/*.java Some test code is provided and can be run with java dict.BinaryTree Familiarize yourself with the fields and methods of the BinaryTree and BinaryTreeNode classes. BinaryTree is an implementation of the Dictionary interface (which you also used in Homework 6) as a binary search tree. Note that BinaryTree uses Comparable objects as keys (since it is an ordered dictionary), whereas in the Dictionary abstract class, keys are declared as plain Objects. Thus you will occasionally need to cast Objects to Comparables. Part I: Finding an Element in a Binary Search Tree (2 points) -------------------------------------------------------------- Complete the implementation of the find() method in dict/BinaryTree.java by filling in the body of findHelper(). find() takes a key as its single parameter, and returns an element associated with that key, or null if there is none. (If there are several elements associated with a key, it doesn't matter which one is returned.) findHelper() helps by recursively finding and returning a node that contains the key (or null if no such node exists). Take a look at insertHelper() for inspiration. find() should run in O(d) time on a tree with depth d. Part II: Removing an Element with a Given Key (2 points) --------------------------------------------------------- Fill in the body of remove() method in BinaryTree.java. remove() takes a key as its single parameter, and removes one item having that key if the tree contains one. (If there are several elements associated with a key, it doesn't matter which one is removed and returned.) remove() returns the same value that find() returns, but should not call find(). However, remove() SHOULD use the findHelper() method you wrote for Part I. remove() should run in O(d) time if the depth of the tree is d. Check-off --------- Show your TA or Lab Assistant the code you have written, and run the test program. You'll receive points for each part that runs correctly. 2 points: If find() works correctly. 1 point: If remove() works for nodes that have no child or one child. 1 point: If remove() works for nodes that have two children.
cs61b_lab11's People
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ๐๐๐
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google โค๏ธ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.