NOTE: This IS homework, so please do not give me the answer right out, but pointers would be helpful.
Assignment overview:
(Test each method to ensure that it works properly.)
Generate a binary search with 100 elements added in the correct order - add the numbers 1 through 100 to the tree in the correct order add 1, then 2, then 3, etc.
Generate a binary search with 100 elements add in revers order - add the numbers 100, 99, 98 and so on.
Generate a binary search with 100 randomly generated elements.
The reason I said a linear array in the question is because the root has to be the first element in the array and then add the rest.
I do not have all the other methods required to properly test if the tree was made properly, and I am about to leave for work. However, I am posting below the start of the algorithm that I think will work, just not sure.
public BST(int[] numbers)
{
node root;
node currentParent;
node previousParent = null;
int i = 1; // skip the root, that will be handled manualy
root = new node(numbers[0]); // first element is the root
currentParent = root;
// handle right hand side of binary tree first
while (i > root.getValue())
{
while (i > currentParent.getValue())
{
node newNode = new node (numbers[i]);
currentParent.setRightChild(newNode);
previousParent = currentParent;
currentParent = newNode;
i++;
} // end inner while
if (previousParent.leftChild == null)
{
node newNode = new node(numbers[i]);
previousParent.leftChild = newNode;
currentParent = newNode;
i++;
} // end if branch
else
{
System.out.println("Hmm, something seems to be wrong!");
} // end else
} // end right side binary tree while
} // end integer array constructor
This is pretty much the whole algorithm, I would have to do it again but reverse the < and > signs (if this is correct). Am I on the right path with this algorithm?
Adding the node class as requested.
public class node
{
node leftChild; // left pointer
node rightChild; // right pointer
int value; // will be the int value inside the node
boolean isLeaf; // boolean for determing if a node is a left node or not
/*
Null constructor for the class. Sets the pointers to null
*/
public node ()
{
leftChild = null;
rightChild = null;
} // end null constructor
/*
Intialzing constructor that will take a single integer as input
*/
public node (int number)
{
leftChild = null;
rightChild = null;
value = number;
} // end intialzing constructor with int input
/*
The setValue method will take the int value inputted from the array into
a new node
*/
public void setValue(int number)
{
value = number;
} // end setValue()
/*
The getValue method will return to the user the value that is stored
inside a specific node.
*/
public int getValue()
{
return value;
} // end getValue()
/*
The setLeftChild method will set the pointers to the nodes left child
which will be a value that is equal or lower to the paret node
*/
public void setLeftChild (node leftChild)
{
this.leftChild = leftChild;
} // end setLeftChild()
/*
The setRightChild method will be the same as setLeftChild above but will
handle setting the nodes right child. The right child will be a value
that is greater than the parent node
*/
public void setRightChild(node rightChild)
{
this.rightChild = rightChild;
} // end setRightChild
/*
the getLeftChild method will return to the user/calling method what the
left child of a given node is.
*/
public node getLeftChild (node currentNode)
{
return leftChild;
} // end getLeftChild()
/*
the getRightChild method is exactly the same as the getLeftChil method
above, except it will return the right child instead
*/
public node getRightChild(node currentNode)
{
return rightChild;
} // end getRightChild()
/*
The setLeaf method will be in charge of manipulating a boolean value and
setting it to true if the node is a left or not
*/
public void setLeaf(boolean leaf)
{
if (leaf == true)
{
isLeaf = true;
} // end if
else
{
isLeaf = false;
} // end else
} // end setLeaf
/*
The getLeaft method will simply return a boolean value that indicates if
the given node is a left node or not
*/
public boolean getLeaf()
{
return isLeaf;
} // end getLeaf()
} // end node class
nodeobject? Also, the assignment sounds like you need to do something liketree.add(1); tree.add(2);instead of having a constructor make the tree from anint[].intin the array, this way you aren't repeating your code. Something like `for(int i = 0; i < numbers.length; i++) { insert(numbers[i]); }