I can insert a node when I hand it off one value at a time. Now I have an ArrayList that contains values that I need to insert.
I was thinking a constructor is called for here but anything I come up with bombs on compile.
Any suggestions?
/**
*
* This program exercises various methods in the BinarySearchTree class
* extended as part of assignment 5.
*
*/
import java.util.*;
public class TestBST {
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
// Test single insert
System.out.println("Tree after inserting the value 8");
tree.insert(8);
System.out.println("Tree size: " + tree.size());
System.out.println("Tree contents: " + tree.toArrayList());
System.out.println("=====================================================");
// Test collections insert
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(4);
list.add(2);
list.add(6);
list.add(1);
list.add(3);
list.add(5);
list.add(7);
list.add(12);
list.add(15);
list.add(14);
list.add(9);
list.add(11);
list.add(13);
System.out.println("Tree after inserting the values in " + list);
tree.insert(list);
}
}
--------------------------------------------------------------------
import java.util.*;
import sun.org.mozilla.javascript.internal.Node;
public class BinarySearchTree<E extends Comparable<? super E>> implements Iterable<E> {
Node root; // Reference to the root node
int size; // Number of nodes in the tree
/*
* A node in the tree contains an object of class E, a reference
* to its parent node (null for the root node), and references to
* its left and right children.
*/
private class Node {
protected E data;
protected Node left;
protected Node right;
protected Node parent;
public Node(E data, Node left, Node right, Node parent) {
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
}
/* A node is a left child of its parent
* if it has a parent and that parent's left
* reference is to this node.
*/
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
/* A node is a right child of its parent
* if it has a parent and that parent's right
* reference is to this node.
*/
public boolean isRightChild() {
return parent != null && this == parent.right;
}
}
BinarySearchTree() {
root = null;
size = 0;
}
/*
* This inserts its parameter into the tree. It uses the
* the binary search tree property to find the only location
* where the new node must be placed.
*/
public void insert(E object) {
root = insert(root, null, object);
System.out.println("in void insert");
}
private Node insert(Node node, Node parent, E object) {
System.out.println("in Node insert");
if (node == null) {
System.out.println("node is null");
size++;
return new Node(object, null, null, parent);
}
int comparison = node.data.compareTo(object);
if (comparison == 0) {
return node;
}
else if (comparison < 0) {
node.right = insert(node.right, node, object);
return node;
}
else {
node.left = insert(node.left, node, object);
return node;
}
}
/*
* This returns an iterator that behaves according to the
* expectations of the Java API Iterator interface. Having
* this allows a for-each loop to be used in iterating over
* the items in a binary search tree, which are retrieved in
* ascending order.
*/
public java.util.Iterator<E> iterator() {
return new Iterator();
}
/*
* The class Iterator implements the Java API Iterator
* interface.
*/
private class Iterator implements java.util.Iterator<E> {
Node current;
public Iterator() {
/*
* Current is initialized to point to the node
* with the minimum value in the tree, which is
* the leftmost node.
*/
current = root;
if (current != null) {
while (current.left != null) {
current = current.left;
}
}
}
.
}