辅导Binary Trees、讲解Java程序语言、辅导TreeNode留学生、讲解Java设计
- 首页 >> Algorithm 算法 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 abstract data 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 have been left as stubs for you to complete.
1. Start by completing the implementation of ArrayBasedBinaryTree
A small main is included in the class that will allow you to test in isolation by compiling and running:
javac ArrayBasedBinaryTree.java
java ArrayBasedBinaryTree
When you are complete, it should insert the given elements and have the expected output for the calls
to the traversal and toString methods.
Tips:
- The calculation of the indices of the left and right subtree is dependent on the index of the root
ie. if root is 0, left is 2i+1 and right is 2i+2, if root is 1, left is 2i and right is 2i+1
convince yourself of this by drawing a tree of height 3 and numbering the elements in a level order
(top to bottom, left to right) starting at 0 and then repeat with a numbering starting at 1
- The traversal methods are the simplest to write recursively – you will need helper methods that
takes the index of a tree element as a parameter much like the recursive list methods you wrote.
BinaryTree
<>
+ 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): voidCHECK POINT – get your lab TA to check off after you have completed this. They will want to see you
compile and run ArrayBasedBinaryTree.java
2. Next complete the implementation of RefBasedBinaryTree
Again, a small main is included in the class allowing you to compile and run:
javac RefBasedBinaryTree.java
java RefBasedBinaryTree
When you are complete it should insert 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 not have the same output.
Take the time to understand what the insert method is doing by hand-drawing the tree that will be
created by the calls to insert in the main method. Use this drawing to ensure your traversal and
toString methods are correct.
Tips:
- The traversal methods are the simplest 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 your lab TA to check off after you have completed this. They will want to see your
hand-drawn tree and see you compile and run RefBasedBinaryTree.java
Part II – Extending BinaryTree
In this part of the lab you will implement the ArrayBasedBinarySearchTree.java and
RefBasedBinarySearchTree.java that will extend 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 new class for that ArrayBasedBinarySearchTree.java that extends
ArrayBasedBinarySearchTree.java
2. Understand which methods you will inherit from the super class
3. Implement the required methods that you will override from the super class (insertion will be much
different as the insert must maintain the invariant of the Binary Search Tree)
4. Add a main to the class to test this class
5. Repeat steps 1-4 for RefBasedBinarySearchTree.java
CHECK POINT – get your lab TA to check off after you have completed this. They will want to see the
methods you implemented in ArrayBasedBinarySearchTree and RefBasedBinarySearchTree
and see you run the main in each.
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 abstract data 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 have been left as stubs for you to complete.
1. Start by completing the implementation of ArrayBasedBinaryTree
A small main is included in the class that will allow you to test in isolation by compiling and running:
javac ArrayBasedBinaryTree.java
java ArrayBasedBinaryTree
When you are complete, it should insert the given elements and have the expected output for the calls
to the traversal and toString methods.
Tips:
- The calculation of the indices of the left and right subtree is dependent on the index of the root
ie. if root is 0, left is 2i+1 and right is 2i+2, if root is 1, left is 2i and right is 2i+1
convince yourself of this by drawing a tree of height 3 and numbering the elements in a level order
(top to bottom, left to right) starting at 0 and then repeat with a numbering starting at 1
- The traversal methods are the simplest to write recursively – you will need helper methods that
takes the index of a tree element as a parameter much like the recursive list methods you wrote.
BinaryTree
<
+ 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): voidCHECK POINT – get your lab TA to check off after you have completed this. They will want to see you
compile and run ArrayBasedBinaryTree.java
2. Next complete the implementation of RefBasedBinaryTree
Again, a small main is included in the class allowing you to compile and run:
javac RefBasedBinaryTree.java
java RefBasedBinaryTree
When you are complete it should insert 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 not have the same output.
Take the time to understand what the insert method is doing by hand-drawing the tree that will be
created by the calls to insert in the main method. Use this drawing to ensure your traversal and
toString methods are correct.
Tips:
- The traversal methods are the simplest 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 your lab TA to check off after you have completed this. They will want to see your
hand-drawn tree and see you compile and run RefBasedBinaryTree.java
Part II – Extending BinaryTree
In this part of the lab you will implement the ArrayBasedBinarySearchTree.java and
RefBasedBinarySearchTree.java that will extend 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 new class for that ArrayBasedBinarySearchTree.java that extends
ArrayBasedBinarySearchTree.java
2. Understand which methods you will inherit from the super class
3. Implement the required methods that you will override from the super class (insertion will be much
different as the insert must maintain the invariant of the Binary Search Tree)
4. Add a main to the class to test this class
5. Repeat steps 1-4 for RefBasedBinarySearchTree.java
CHECK POINT – get your lab TA to check off after you have completed this. They will want to see the
methods you implemented in ArrayBasedBinarySearchTree and RefBasedBinarySearchTree
and see you run the main in each.