0 Replies - 336 Views - Last Post: 15 July 2010 - 08:36 PM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12634
  • View blog
  • Posts: 45,801
  • Joined: 27-December 08

Tree Data Structure

Posted 15 July 2010 - 08:36 PM

Description: Models a Tree Data Structure. Instantiate a generic Tree object and use that to manage the Tree.
/**
 * @author Macosxnerd101
 * @date 7/12/2010
 *
 * This class modifies a Tree data structure implementing the Collection Interface.
 * It has a single Root Node, which has a single value of type E, and n children.
 */

import java.util.*;


public class Tree<E>{

	private TreeNode<E> root;

	public Tree(){
		root = new TreeNode<E>();
	}

	private Tree(TreeNode<E> root){
		this.root = root;
	}

	/**
	 * @param value: The element to add to the Tree
	 * @return boolean: true if the element was added, false otherwise
	 *
	 * This method adds the value to the End of the root Node
	 * */
	public boolean add(E value) {
		if(root.getValue() == null){
			root.setValue(value);
			return true;
		}

		return root.add(new TreeNode<E>(value));
	}


    /**
     * @param arg0: The Collection to add to the Tree
     * @return boolean: Whether or not the add was successful
     *
     * Adds all the elements to the root Node of this tree
     * */
	public boolean addAll(Collection<? extends E> arg0) {
		Iterator<? extends E> iterate = arg0.iterator();

		while(iterate.hasNext())
			add(iterate.next());

		return true;
	}

    /**
     * @param depth: How deep to go to add the element
     * @param path: The path to travel to get to the desired node
     * @param value: The value to add
     * @return boolean: Whether or not the add was successful
     *
     * Invokes the helper add() overload to handle insertion
     * */
	public boolean add(int depth, int[] path, E value){
		return add(depth, path, -1, value);
	}

	/**
	 * @param index: The specific child node for a root node to hold value
	 *
	 * All other params are the same as the add(int, int, E) method.
	 * Invokes the helper method add(TreeNode<E>, int, int, int[], int, E)
	 * to handle insertion.
	 **/
	public boolean add(int depth, int[] path, int index, E value){
		return add(root, depth, depth, path, index, value);
	}

	/**
	 * @param root: The root element to begin the insertion
	 * @param depth: How deep to traverse to find the insertion point
	 * @param remaining: The number of levels to go until the insertion point
	 * @path path: The specific path of travel to get to the insertion point.
	 			   The element in the array	is accessed by the difference in remaining
	 			   and depth.
	 * @param index: The index of the new Child node
	 * @param value: The value to insert
	 * */
	private boolean add(TreeNode<E> root, int depth, int remaining, int[] path, int index, E value){

		//if we have reached a dead end and still have more to go,
		//throw an Exception
		if(root.numberChildren() == 0 && remaining > 1)
			throw new IllegalArgumentException("The depth of the tree is not as deep as you are trying to traverse: "
				+ "depth = " + (depth-remaining) + "nremaining: " + remaining + "."
			);

		//stop at the parent node we are supposed to insert at
		//and insert the Node
		if(remaining == 1){
			if(index > 0 && index < root.numberChildren()){
				root.add(index, new TreeNode<E>(value));
			}
			else{
				root.add(new TreeNode<E>(value));
			}
			return true;
		}

		//otherwise, recurse based on the next node
		return add(root.get(path[depth-remaining]), depth, --remaining, path, index, value);

	}



	//clears the Tree by destroying the root
	public void clear() {
		root = new TreeNode<E>();
	}

	/**
	 * @param object: The Object to search for
	 * @return boolean: Whether or not the Object was found in the Tree
	 *
	 * Invokes overloaded helper method to search for the element
	 * */
	public boolean contains(Object object) {
		return contains(root, object);
	}


	/**
	 * @param root: The root node to begin searching from
	 * @param target: The element to look for
	 * @ return boolean: Whether or not the element was found
	 * */
	private boolean contains(TreeNode<E> root, Object target){

                if(root.getValue() == null) return false;
		//if we've found a match, great
		if(root.getValue().equals(target)) return true;


		//otherwise, let's take a look at the Children Nodes
		//and check a sub-tree
		for(int i = 0; i < root.numberChildren(); i++){
			if(contains(root.get(i), target))
				return true;
		}

		//if we don't find a match, oh well
		return false;

	} //end contains()


	/**
	 * @param arg0: The Collection of elements to find in the tree
	 * @return boolean: True if all the elements were found
	 * */
	public boolean containsAll(Collection<?> arg0) {
		for(Object c:arg0){
			if(!contains(c))
				return false;
		}
		return true;
	}


	//the Tree is empty if the root Node doesn't have a value
	//and doesn't have any child Nodes
	public boolean isEmpty() {
		return root.numberChildren() == 0 && root.getValue() == null;
	}

	/**
	 * @return null: Not allowing for an Iterator
	 * */
	public Iterator<E> iterator() {
		return null;
	}

	/**
	 * @param object: The Value to remove from the Tree
	 * @return boolean: If the element was found and removed
	 *
	 * Invokes the helper overload remove() to handle the removal.
	 * Removes the first instance of the element
	 * */
	public boolean remove(Object object) {
                return remove(root, object, 0, true);
	}

	/**
	 * @param object: The Object to search for
	 * */
	public boolean remove(Object object, int slideUp, boolean deleteAll){
		return remove(root, object, slideUp, deleteAll);
	}

	/**
	 * @param root: The root Node scope to begin the removal
	 * @param object: The object to remove
	 * @param slideUp: The index of the Child Node to replace the parent node, keeping the dependencies in tact
	 * @param deleteAll: Determines whether to delete a node and its children, or move up a child to replace it
	 *                   When deleteAll == true, slideUp is ignored
	 * @return boolean: Whether or not the remove was a success
	 * */
	private boolean remove(TreeNode<E> root, Object object, int slideUp, boolean deleteAll){

		//because the approaches for completely removing a node
		//and promoting one of its children are different, I have
		//two separate approaches configured
		if(deleteAll){

			for(int i = 0; i < root.numberChildren(); i++){
				if(root.get(i).getValue().equals(object)){
					System.out.println(root.remove(i));
					return true;
				}//end if
			}//end for

		}//end if

		//if we are sliding up
		else{

			//then it will only happen if we find the target
			if(root.getValue().equals(object)){
				if(root.numberChildren() > 0){
                                    overwrite(root, root.get(slideUp));
                                    return true;
                                }
                                return false;
			}

			//otherwise, recursively check the children
			for(int i = 0; i < root.numberChildren(); i++){
				if(remove(root.get(i),object, slideUp, deleteAll))
					return true;
			}
		} //end else

		return false;
	} //end remove


	/**
	 * @param one: The TreeNode to be overwritten
	 * @param two: The node to be slidden up
	 *
	 * This method overwrites one with the children and value in two.
	 * The connections from one are maintained, and two is essentially
	 * promoted. The order of the Children are that two's children are first,
	 * followed by one's children as defined by the ArrayList addAll() method.
	 * */
	private void overwrite(TreeNode<E> one, TreeNode<E> two){
		two.addAll(one.getConnections());
		two.remove(two);
		one.setNode(two);

	} //end overwrite


	/**
	 * @param arg0: The Collection of elements to remove from the tree
	 * @return boolean: True if all the elements were removed, false otherwise
	 * */
	public boolean removeAll(Collection<?> arg0) {
		boolean remove = true;

		Iterator<?> i = arg0.iterator();
		while(i.hasNext()){
			if(!remove(i))
				remove = false;
		}
		return remove;
	} //end removeAll()

 	/**
 	 * @return int: The number of Nodes in this Tree
 	 * */
	public int size() {
		return size(root);
	}

	/**
	 * @param root: The root Node of the Tree we are interested in
	 * @return int: The number of Nodes in this Tree
	 * */
	public int size(TreeNode<E> root){

		//to prevent NullPointerExceptions for null roots
		if(root == null) return 0;

		int sum = 1; //great, we have one Node- the param

		//repeat this process for subtrees based off the children
		for(int i = 0; i < root.numberChildren(); i++){
			sum += size(root.get(i));
		}

		return sum;
	} //end size()


	/**
	 * @return Object[]: The depth-first representation of the Tree
	 * */
	public Object[] toArray() {
		LinkedList<E> list = new LinkedList<E>();
		populate(list, root);
		return list.toArray();
	} //end toArray()


	/**
	 * @param list: The LinkedList to populate
	 * @param root: The root node to begin populating the List from
	 *
	 * Populates the LinkedList using a depth-first traversal
 	 * */
	private void populate(LinkedList<E> list, TreeNode<E> root){
		list.add(root.getValue());

		if(root.numberChildren() == 0) return;

		for(int i = 0; i < root.numberChildren(); i++)
			populate(list, root.get(i));
	} //end populate()


	/**
	 * @param array: The array to populate. As the user would be
	 * */
	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] array) {
		array = (T[])toArray();
		return array;
	} //end toArray()


	/**
	 * @return int: The number of levels deeep the tree is
	 *
	 * Invokes a helper method to traverse the tree to it's greatest depth
	 * */
	public int depth(){
		return depth(root);
	}

	/**
	 * @param root: The root Node to find the depth for
	 * @return int: The depth of the Tree from root
	 * */
	public int depth(TreeNode<E> root){

		//if we have a null root or no children, we have no depth
		if(root == null || root.numberChildren() == 0) return 0;

		//start at the lowest
		int max = Integer.MIN_VALUE;

		for(int i = 0; i < root.numberChildren(); i++){
			max = Math.max(depth(root.get(i)), max);
		}

		//if(root.numberChildren() == 1) return 1 + depth(root.get(0));

		if(max < 0) max = 0;

		return 1 + max;
	}

	public String toString(){
		return root.toString();
	}

	/**
	 * @param depth: The depth of where to find the root for the sub-tree
	 * @param path: The path to travel to find the root node
	 * @return Tree<E>: Returns a Tree with the desired Node as the root Node
	 * */
	public Tree<E> subTree(int depth, int[] path){
		int remaining = depth;
		TreeNode<E> temp = root;

		while(remaining > 0 && temp.numberChildren() > 0){

			if(path == null || path.length < depth)
				temp = temp.get(0);

			else
				temp = temp.get(path[depth-remaining]);

			remaining--;
		}
		if(remaining > 0){
			throw new IllegalArgumentException("Attempting to traverse too deeply: depth = " + depth()
				+ ", requested depth = " + depth);
		}

		return new Tree<E>(temp);
	} //end subtree

	/**
	 * @return root: The root Node of this Tree
	 * */
	public TreeNode<E> getRoot(){
		return root;
	}

}

/**
 * @author Macosxnerd101
 * @date 7/12/2010
 *
 * Describes a Single Node in a Tree. No limit on children
 * */

import java.util.*;

public class TreeNode<E> {

	private E value;

	//children nodes
	private List<TreeNode<E>> connections;

	//initialize with no value
	public TreeNode(){
		this(null);
	}

	/**
	 * @param: The value to initialize the Node with
	 * */
	public TreeNode(E value){
		this.value = value;
		connections = new ArrayList<TreeNode<E>>();
	}

	/**
	 * @return E: The value of this Node
	 * */
	public E getValue(){return value;}

	/**
	 * @param value: The new Value for this Node
	 * */
	public void setValue(E value){this.value = value;}

	/**
	 * @param value: The new Child TreeNode to add to this Node
	 * @return boolean: Whether or not the Node was added. See java.util.ArrayList.add(E elem);
	 * */
	public boolean add(TreeNode<E> value){
		return connections.add(value);
	}

	/**
	 * @param index: The index to add the Node
	 * @param value: The Node to add
	 * See java.util.ArrayList.add(int index, E elem);
	 **/
	public void add(int index, TreeNode<E> value){
		connections.add(index,value);
	}

	/**
	 * @param collect: The Collection of TreeNodes to add
	 * See java.util.ArrayList.addAll(Colllection<? super E>);
	 * */
	public void addAll(Collection<? extends TreeNode<E>> collect){
		connections.addAll(collect);
	}

	/**
	 * @param index: The index to set the Node
	 * @param value: The TreeNode to be set for that index
	 * @param overwrite: Whether or not the Children Nodes at connections.get(index)
	 * */
	public void set(int index, TreeNode<E> value, boolean overwrite){

		//if we're going to overwrite, and can overwrite, then do such
		if(overwrite ^ (overwrite && value.connections == null))
			value.connections = connections.get(index).connections;

		//otherwise, add the Children Nodes to the new Node
		else value.connections.addAll(connections.get(index).connections);

		connections.set(index,value);
	}

	//clears the Children for this Node
	public void clear(){
		connections.clear();
	}

	/**
	 * @param index: The index of the Child Node to get
	 * @return TreeNode<E>: The Child Node at index
	 * */
	public TreeNode<E> get(int index){
		return connections.get(index);
	}

	/**
	 * @param elem: The TreeNode to search for
	 * @return int: The index of the TreeNode
	 * @return -1: If the Node isn't found
	 * */
	public int get(TreeNode<E> elem){
		for(int i = 0; i < connections.size(); i++){
			if(connections.get(i).equals(elem)) return i;
		}
		return -1;
	}

	/**
	 * @return List<TreeNode<E>>: The List of Children Nodes
	 * */
	public List<TreeNode<E>> getConnections(){return connections;}

	/**
	 * @return int: The number of Children Nodes for this Node
	 * */
	public int numberChildren(){return connections.size();}

	/**
	 * @param index: The index to remove
	 * @return TreeNode<E>: The Node that was removed
	 *
	 * See java.util.ArrayList.remove(int index)
	 * */
	public TreeNode<E> remove(int index){
		return connections.remove(index);
	}

        /**
         * @param node: The Node to remove
         * */
	public void remove(TreeNode<E> node){
		connections.remove(node);
	}

        /**
         * @param overwrite: The TreeNode to overwrite with
         *
         * This method acts like a copy constructor without creating
         * a new TreeNode object
         * */
	public void setNode(TreeNode<E> overwrite){
		this.connections = overwrite.connections;
		this.value = overwrite.value;
	}

	public String toString(){
		String rep = value + "nChildren:n";

		if(numberChildren() == 0) rep += "Nonenn";

		else{
			rep += "n";
			for(int i = 0; i < numberChildren(); i++)
				rep += connections.get(i) + "nn";
		}
		return rep;
	}

}




Is This A Good Question/Topic? 0
  • +

Page 1 of 1