Skip to Main Content

New to Java

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

ArrayList members to binary tree nodes

843785Mar 12 2009 — edited Mar 13 2009
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;
				}
			}
		}
.
}
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Apr 10 2009
Added on Mar 12 2009
10 comments
2,760 views