代写Binary Trees、代做Java程序语言、代写TreeNode留学生、代做Java设计

日期：2019-07-11 08:35

Lab 8

Objectives

Introduction to Binary Trees and Binary Search Trees

Practice with implementing an interface with both reference and array based implementations

Practice with extending a class and overriding methods

Part I – implementing a BinaryTree interface

The following is a UML representation of a BinaryTree abstractdata type. We have provided you with

the interface BinaryTree.java and the classes ArrayBasedBinaryTree.java,

RefBasedBinaryTree.java and TreeNode.java. The methods in ArrayBasedBinaryTree and

RefBasedBinaryTree havebeen left as stubs for you to complete.

1. Start by completing the implementation of ArrayBasedBinaryTree

A smallmain isincluded in theclass that willallow you to test in isolation by compiling and running:

javac ArrayBasedBinaryTree.java

java ArrayBasedBinaryTree

When you are complete, it should insertthe given elements and have the expected output forthe calls

to the traversal and toString methods.

Tips:

- The calculation of the indices of theleft and right subtree is dependent on the index ofthe root

ie. if root is 0, left is 2i+1 and right is 2i+2, if root is 1, leftis 2i and right is2i+1

convince yourself of this by drawing a tree of height 3 and numbering the elements in a level order

(top tobottom,left toright) startingat 0 and then repeat with a numbering starting at1

- The traversal methodsare thesimplest to write recursively – you will need helper methodsthat

takes the indexof a tree element as a parameter much like the recursive list methods you wrote.

BinaryTree

<<interface>>

+ insert(): void

+ inOrder(): void

+ preOrder(): void

+ postOrder(): void

+ toString(): String

RefBasedBinaryTree

# root: TreeNode

+ RefBasedBinaryTree()

+ insert(Integer): void

# height(int): void

+ toString(): String

ArrayBasedBinaryTree

# CAPACITY: int

# data: Integer[]

# root: int

# size: int

+ ArrayBasedBinaryTree()

+ insert(Integer): void

# getLeft(int): int

# getRight(int): int

+ toString(): String

TreeNode

# data: Integer

# left: TreeNode

# right: TreeNode

+ TreeNode(Integer)

+ getValue(): Integer

+ setValue(Integer): void

+ getLeft(): TreeNode

+ setLeft(TreeNode): void

+ getRight(): TreeNode

+ setRight(TreeNode): void

ArrayBasedBinarySearchTree

+ ArrayBasedBinaryTree()

+ insert(Integer)

RefBasedBinarySearchTree

+ RefBasedBinarySearchTree()

+ insert(Integer): void

CHECK POINT – get your lab TA tocheck off afteryouhave completed this. They will want to see you

compile and run ArrayBasedBinaryTree.java

2. Nextcomplete the implementation of RefBasedBinaryTree

Again,a smallmain isincluded in theclass allowing you to compileandrun:

javac RefBasedBinaryTree.java

java RefBasedBinaryTree

When you are complete it shouldinsert the given elements and have the expected output for the calls to

the traversal and toString methods.

NOTE: the insertion algorithm is not the same as the ArrayBasedBinaryTree implementation so

the traversals will nothave the same output.

Take the time to understand what the insert method is doing by hand-drawing the tree that will be

createdby the calls toinsert in the main method. Use this drawing to ensure your traversal and

toString methods are correct.

Tips:

- The traversalmethodsare thesimplest to write recursively – you will need helper methods that

take a TreeNode as a parameter much like the recursive list methods you wrote.

CHECK POINT – get yourlab TA to checkoff after you have completedthis. They willwant tosee your

hand-drawn treeand seeyou compile andrun RefBasedBinaryTree.java

Part II – Extending BinaryTree

In thispart of the labyou will implement the ArrayBasedBinarySearchTree.java and

RefBasedBinarySearchTree.java that willextend the ArrayBasedBinaryTree.java and

RefBasedBinaryTree.java respectively (as shown in the UML).

RECALL:A Binary Search Tree maintains the invariant that for every element in the tree, every element in

its left subtree must be smaller than the parent and every element in its right subtree must be larger than

the parent

1. Create a newclass for that ArrayBasedBinarySearchTree.java that extends

ArrayBasedBinarySearchTree.java

2. Understand which methods youwill inherit from the super class

3. Implement the required methods that you willoverride from the super class (insertion will be much  

different as the insertmust maintain the invariant of the Binary Search Tree)

4. Add a main to the class to test thisclass

5. Repeat steps1-4 forRefBasedBinarySearchTree.java

CHECK POINT – get yourlab TA to checkoff after you have completed this. They will want to see the

methodsyou implementedin ArrayBasedBinarySearchTree and RefBasedBinarySearchTree

and seeyou runthe main in each.