Question
In Java, implement a Binary Search Tree in an array. (Except we will not have need to delete anything.) I will provide you with an
In Java, implement a Binary Search Tree in an array. (Except we will not have need to delete anything.) I will provide you with an array class that you must use to implement your BST. My class is based on an ArrayList, but takes care of accessing nodes beyond the end of the array. (With any set or get, I increase the size if necessary and fill with nulls.)
You may not use a linked implementation. You will use 2i+1, 2i+2, and (i-1)/2 to traverse the tree.
The data will be a text file containing words. Assume a word is whatever is returned by the Scanner.next() method. Duplicate words will be ignored.
Open a file called GA.txt. Using the Scanner class, read each word, convert to uppercase, and
1. insert it into a BST
2. use a BST method to find and print the minimum value
3. use a BST method to find and print the maximum value
4. print the tree inorder
5. print the tree preorder
6. print the tree postorder
BST methods that you should implement: empty(), insert(String), min(), max(), inOrder(), preOrder(), and postOrder(), along with the following utility methods leftChild(int), rightChild(int), parent(int), and toString().
Dont forget to use compareTo for your strings.
--------------------------------------------------------
Sample input: eee bbb xxx aaa ccc yyy zzz ddd
Sample output (with the array shown for debugging):
[EEE, BBB, XXX, AAA, CCC, null, YYY, null, null, null, DDD, null, null, null, ZZZ]
min: AAA
max: ZZZ
inorder:
AAA
BBB
CCC
DDD
EEE
XXX
YYY
ZZZ
preorder:
EEE
BBB
AAA
CCC
DDD
XXX
YYY
ZZZ
postorder:
AAA
DDD
CCC
BBB
ZZZ
YYY
XXX
EEE
Fourscore and seven years ago our fathers brought forth on this continent a new nation conceived in
Liberty and dedicated to the proposition that all men are created equal
min: A
max: YEARS
inorder:
A
AGO
ALL
AND
ARE
BROUGHT
CONCEIVED
CONTINENT
CREATED
DEDICATED
EQUAL
FATHERS
FORTH
FOURSCORE
IN
LIBERTY
MEN
NATION
NEW
ON
OUR
PROPOSITION
SEVEN
THAT
THE
THIS
TO
YEARS
preorder:
FOURSCORE
AND
AGO
A
ALL
FATHERS
BROUGHT
ARE
CONTINENT
CONCEIVED
DEDICATED
CREATED
EQUAL
FORTH
SEVEN
OUR
ON
NEW
NATION
IN
LIBERTY
MEN
PROPOSITION
YEARS
THIS
THE
THAT
TO
postorder:
A
ALL
AGO
ARE
CONCEIVED
CREATED
EQUAL
DEDICATED
CONTINENT
BROUGHT
FORTH
FATHERS
AND
MEN
LIBERTY
IN
NATION
NEW
ON
PROPOSITION
OUR
THAT
THE
TO
THIS
YEARS
SEVEN
FOURSCORE
--------------------------------------------------------------------------
HERE IS SOME OF THE CODE:
import java.util.ArrayList; /* This class is to be used as the basis for your BST class * Declare, construct and use a pmmArrayList in your BST * (this is composition, as opposed to inheritance) * YOU MAY NOT CHANGE THIS CODE... * I will use my own copy of this code, not yours. * If someone finds an error, I will post a fix for everyone to use. */ public class pmmArrayList
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started