13 Replies - 3723 Views - Last Post: 20 April 2011 - 10:54 AM

#1 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Save The Trees Challenge

Post icon  Posted 18 April 2011 - 02:30 PM

It's time to go green with some of my personal favorite Al Goreithms. For this challenge, post something you have done with a Tree data structure. It can be implementing a specific Tree like an AVL Tree to an algorithm like Prim's algorithm, or something completely different. The only constraint is that you use Trees, your submission is written in a programming language, not simply pseudo-code, and you post it using spoiler tags. So let's have some fun and fight global warming!

Submission 1:
Spoiler


Submission 2:
Spoiler


Is This A Good Question/Topic? 2
  • +

Replies To: Save The Trees Challenge

#2 Sergio Tapia   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1258
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Save The Trees Challenge

Posted 18 April 2011 - 07:41 PM

*
POPULAR

My attempt at using trees in an application:

Console.WriteLine(@"

         ,
                      dM
                      MMr
                     4MMML                  .
                     MMMMM.                xf
     .              "M6MMM               .MM-
      Mh..          +MM5MMM            .MMMM
      .MMM.         .MMMMML.          MMMMMh
       )MMMh.        MM5MMM         MMMMMMM
        3MMMMx.     'MMM3MMf      xnMMMMMM"
        '*MMMMM      MMMMMM.     nMMMMMMP"
          *MMMMMx    "MMM5M\    .MMMMMMM=
           *MMMMMh   "MMMMM"   JMMMMMMP
             MMMMMM   GMMMM.  dMMMMMM            .
              MMMMMM  "MMMM  .MMMMM(        .nnMP"
   ..          *MMMMx  MMM"  dMMMM"    .nnMMMMM*
    "MMn...     'MMMMr 'MM   MMM"   .nMMMMMMM*"
     "4MMMMnn..   *MMM  MM  MMP"  .dMMMMMMM""
       ^MMMMMMMMx.  *ML "M .M*  .MMMMMM**"
          *PMMMMMMhn. *x > M  .MMMM**""
             ""**MMMMhx/.h/ .=*"
                      .3P"%....
                   nP"     "*MMnx 


");



:pirate:

This post has been edited by Sergio Tapia: 18 April 2011 - 08:21 PM

Was This Post Helpful? 5
  • +
  • -

#3 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: Save The Trees Challenge

Posted 18 April 2011 - 08:17 PM

LOL! Trees Sergio, not weed!
Was This Post Helpful? 2
  • +
  • -

#4 Brewer   User is offline

  • Awesome
  • member icon

Reputation: 182
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: Save The Trees Challenge

Posted 18 April 2011 - 10:46 PM

On an unrelated note, I don't think I've ever seen macosxnerd101 use "lol" in one of his posts.

Maybe I'll get around to trying something of my way.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: Save The Trees Challenge

Posted 19 April 2011 - 01:35 PM

Let's get some more entries everyone! Trees are some fun stuff! Surely somebody has done something with Trees like tree traversals, reverse polish notation, etc. Let's have some fun with this!

I've got another submission, for binary tree rotations:
Spoiler

Was This Post Helpful? 0
  • +
  • -

#6 dorknexus   User is offline

  • or something bad...real bad.
  • member icon

Reputation: 1272
  • View blog
  • Posts: 4,625
  • Joined: 02-May 04

Re: Save The Trees Challenge

Posted 19 April 2011 - 03:04 PM

Quote

LOL! Trees Sergio, not weed!


Pssh. If you were in the know, you'd know that trees are synonymous. People who smoke trees are are called Ents. YOU LOSE.
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: Save The Trees Challenge

Posted 19 April 2011 - 03:09 PM

Actually, this is an Ent.
Posted Image
Was This Post Helpful? 1
  • +
  • -

#8 Brewer   User is offline

  • Awesome
  • member icon

Reputation: 182
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: Save The Trees Challenge

Posted 19 April 2011 - 03:21 PM

Lord of the Rings ftw.
Was This Post Helpful? 0
  • +
  • -

#9 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Save The Trees Challenge

Posted 19 April 2011 - 04:08 PM

See Blog Post: Generic Binary Tree
Was This Post Helpful? 1
  • +
  • -

#10 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: Save The Trees Challenge

Posted 19 April 2011 - 04:16 PM

Awesome entry Adam! It was nice to see the BTree reprsented as well!
Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Save The Trees Challenge

Posted 19 April 2011 - 04:19 PM

I don't think it a proper b-tree. Is it?
Was This Post Helpful? 0
  • +
  • -

#12 Nikitin   User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: Save The Trees Challenge

Posted 19 April 2011 - 06:10 PM

That's not a B-Tree.
Was This Post Helpful? 0
  • +
  • -

#13 Ronald91   User is offline

  • New D.I.C Head

Reputation: 11
  • View blog
  • Posts: 31
  • Joined: 26-April 09

Re: Save The Trees Challenge

Posted 20 April 2011 - 10:29 AM

Here is an implementation of a binary tree that I used recently.

package TreePackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
import StackAndQueuePackage.*;

/**
 * A class that implements the ADT binary tree.
 */
public class BinaryTree<T> implements BinaryTreeInterface<T>, java.io.Serializable
{
  private BinaryNodeInterface<T> root;
  
  public BinaryTree()
  {
    root = null;
  } // end default constructor
  
  public BinaryTree(T rootData)
  {
    root = new BinaryNode<T>(rootData);
  } // end constructor
  
  public BinaryTree(T rootData, BinaryTree<T> leftTree, 
                                BinaryTree<T> rightTree)
  {
    privateSetTree(rootData, leftTree, rightTree);
  } // end constructor
  
  public void setTree(T rootData)
  {
    root = new BinaryNode<T>(rootData);
  } // end setTree
  
  public void setTree(T rootData, BinaryTreeInterface<T> leftTree,
                                  BinaryTreeInterface<T> rightTree)
  {
    privateSetTree(rootData, (BinaryTree<T>)leftTree, 
                             (BinaryTree<T>)rightTree);
  } // end setTree

	// 26.08
	private void privateSetTree(T rootData, BinaryTree<T> leftTree, 
	                                        BinaryTree<T> rightTree)
	{
	  root = new BinaryNode<T>(rootData);
	  
	  if ((leftTree != null) && !leftTree.isEmpty())
	    root.setLeftChild(leftTree.root);
	    
	  if ((rightTree != null) && !rightTree.isEmpty())
	  {
	    if (rightTree != leftTree)
	      root.setRightChild(rightTree.root);
	    else
	      root.setRightChild(rightTree.root.copy());
	  } // end if
	  
	  if ((leftTree != null) && (leftTree != this))
	    leftTree.clear(); 
	    
	  if ((rightTree != null) && (rightTree != this))
	    rightTree.clear();
	} // end privateSetTree


	private BinaryNode<T> copyNodes() // not essential
	{
		return (BinaryNode<T>)root.copy();
		
	} // end copyNodes

	// 26.09
	public T getRootData()
	{
	  T rootData = null;
	  
	  if (root != null)
	    rootData = root.getData();
	    
	  return rootData;
	} // end getRootData

	// 26.09
	public boolean isEmpty()
	{
	  return root == null;
	} // end isEmpty

	// 26.09
	public void clear()
	{
	  root = null;
	} // end clear

	// 26.09
	protected void setRootData(T rootData)
	{
	  root.setData(rootData);
	} // end setRootData

	// 26.09
	protected void setRootNode(BinaryNodeInterface<T> rootNode)
	{
	  root = rootNode;
	} // end setRootNode

	// 26.09
	protected BinaryNodeInterface<T> getRootNode()
	{
	  return root;
	} // end getRootNode

	// 26.10
	public int getHeight()
	{
	  return root.getHeight();
	} // end getHeight

	// 26.10
	public int getNumberOfNodes()
	{
	  return root.getNumberOfNodes();
	} // end getNumberOfNodes

	// 26.12
	public void inorderTraverse() 
	{
	  inorderTraverse(root);
	} // end inorderTraverse

	private void inorderTraverse(BinaryNodeInterface<T> node) 
	{
	  if (node != null)
	  {
	    inorderTraverse(node.getLeftChild());
	    System.out.println(node.getData());
	    inorderTraverse(node.getRightChild());
	  } // end if
	} // end inorderTraverse

	public Iterator<T> getPreorderIterator()
	{
		return new PreorderIterator();	
	} // end getPreorderIterator

	// 26.13
	public Iterator<T> getInorderIterator()
	{
		return new InorderIterator();	
	} // end getInorderIterator
	
	public Iterator<T> getPostorderIterator()
	{
		return new PostorderIterator();	
	} // end getPostorderIterator

	public Iterator<T> getLevelOrderIterator()
	{
		return new LevelOrderIterator();	
	} // end getLevelOrderIterator

/*
	// 26.14 ITERATIVE
	public void inorderTraverse()
	{
	  StackInterface<BinaryNodeInterface<T>> nodeStack = 
	                           new LinkedStack<BinaryNodeInterface<T>>();
	  BinaryNodeInterface<T> currentNode = root;
	  
	  while (!nodeStack.isEmpty() || (currentNode != null))
	  {
	    // find leftmost node with no left child
	    while (currentNode != null)
	    {
	      nodeStack.push(currentNode);
	      currentNode = currentNode.getLeftChild();
	    } // end while
	    
	    // visit leftmost node, then traverse its right subtree
	    if (!nodeStack.isEmpty())
	    {
	      BinaryNodeInterface<T> nextNode = nodeStack.pop();
	      assert nextNode != null; // since nodeStack was not empty
	                               // before the pop
	      System.out.println(nextNode.getData());
	      currentNode = nextNode.getRightChild();
	    } // end if
	  } // end while
	} // end inorderTraverse

	public void inorderTraverse() // Q5
	{
		StackInterface<BinaryNode<T>> nodeStack = new LinkedStack<BinaryNode<T>>();
		BinaryNode<T> currentNode = (BinaryNode<T>)root;//(BinaryNode<T>)
		
		while (!nodeStack.isEmpty() || (currentNode != null))
		{
			while (currentNode != null)
			{
				nodeStack.push(currentNode);
				currentNode = (BinaryNode<T>)currentNode.getLeftChild();	//(BinaryNode<T>)
			} // end while

			if (!nodeStack.isEmpty())
			{
				BinaryNode<T> nextNode = nodeStack.pop();				
				assert nextNode != null; // since stack was not empty before pop
				System.out.print(nextNode.getData() + " ");
				currentNode = (BinaryNode<T>)nextNode.getRightChild();	//(BinaryNode<T>)
			}
		}
		System.out.println();
	} // end inorderTraverse

*/
	private class PreorderIterator implements Iterator<T>
	{
		private StackInterface<BinaryNodeInterface<T>> nodeStack;
		
		public PreorderIterator()
		{
			nodeStack = new LinkedStack<BinaryNodeInterface<T>>();
			if (root != null)
				nodeStack.push(root);
		} // end default constructor
		
		public boolean hasNext() 
		{
			return !nodeStack.isEmpty();
		} // end hasNext
		
		public T next()
		{
			BinaryNodeInterface<T> nextNode;
			
			if (hasNext())
			{
				nextNode = nodeStack.pop();
				BinaryNodeInterface<T> leftChild = nextNode.getLeftChild();
				BinaryNodeInterface<T> rightChild = nextNode.getRightChild();
				
				// push into stack in reverse order of recursive calls
				if (rightChild != null)
					nodeStack.push(rightChild);
					
				if (leftChild != null)
					nodeStack.push(leftChild);
			}
			else
			{
				throw new NoSuchElementException();
			}
		
			return nextNode.getData();
		} // end next
	
		public void remove()
		{
			throw new UnsupportedOperationException();
		} // end remove
	} // end PreorderIterator

	// 26.15
	private class InorderIterator implements Iterator<T>
	{
	  private StackInterface<BinaryNodeInterface<T>> nodeStack;
	  private BinaryNodeInterface<T> currentNode;
	  
	  public InorderIterator()
	  {
	    nodeStack = new LinkedStack<BinaryNodeInterface<T>>();
	    currentNode = root;
	  } // end default constructor
	  
	  public boolean hasNext() 
	  {
	    return !nodeStack.isEmpty() || (currentNode != null);
	  } // end hasNext
	  
	  public T next()
	  {
	    BinaryNodeInterface<T> nextNode = null;
	    
	    // find leftmost node with no left child
	    while (currentNode != null)
	    {
	      nodeStack.push(currentNode);
	      currentNode = currentNode.getLeftChild();
	    } // end while
	    
	    // get leftmost node, then move to its right subtree
	    if (!nodeStack.isEmpty())
	    {
	      nextNode = nodeStack.pop();
	      assert nextNode != null; // since nodeStack was not empty
	                               // before the pop
	      currentNode = nextNode.getRightChild();
	    }
	    else
	      throw new NoSuchElementException();
	      
	    return nextNode.getData(); 
	  } // end next
	  
	  public void remove()
	  {
	    throw new UnsupportedOperationException();
	  } // end remove
	} // end InorderIterator

	private class PostorderIterator implements Iterator<T>
	{
		private StackInterface<BinaryNodeInterface<T>> nodeStack;
		private BinaryNodeInterface<T> currentNode;
		
		public PostorderIterator()
		{
			nodeStack = new LinkedStack<BinaryNodeInterface<T>>();
			currentNode = root;
		} // end default constructor
		
		public boolean hasNext() 
		{
			return !nodeStack.isEmpty() || (currentNode != null);
		} // end hasNext
		
		public T next()
		{
			boolean foundNext = false;
			BinaryNodeInterface<T> leftChild, rightChild, nextNode = null;
			
			// find leftmost leaf
			while (currentNode != null)
			{
				nodeStack.push(currentNode);
				leftChild = currentNode.getLeftChild();
				if (leftChild == null)	
					currentNode = currentNode.getRightChild();
				else
					currentNode = leftChild;
			} // end while
			
			// stack is not empty either because we just pushed a node, or
			// it wasn't empty to begin with since hasNext() is true.
			// But Iterator specifies an exception for next() in case
			// hasNext() is false.
			
			if (!nodeStack.isEmpty())
			{
				nextNode = nodeStack.pop();
				// nextNode != null since stack was not empty before pop

				BinaryNodeInterface<T> parent = nodeStack.peek();
				
				if (parent != null && nextNode == parent.getLeftChild())
					currentNode = parent.getRightChild();	
				else
					currentNode = null;
			}
			else
			{
				throw new NoSuchElementException();
			} // end if
			
			return nextNode.getData();
		} // end next

		public void remove()
		{
			throw new UnsupportedOperationException();
		} // end remove
	} // end PostorderIterator
	
	private class LevelOrderIterator implements Iterator<T>
	{
		private QueueInterface<BinaryNodeInterface<T>> nodeQueue;
		
		public LevelOrderIterator()
		{
			nodeQueue = new LinkedQueue<BinaryNodeInterface<T>>();
			if (root != null)
				nodeQueue.enqueue(root);
		} // end default constructor
		
		public boolean hasNext() 
		{
			return !nodeQueue.isEmpty();
		} // end hasNext
		
		public T next()
		{
			BinaryNodeInterface<T> nextNode;
			
			if (hasNext())
			{
				nextNode = nodeQueue.dequeue();
				BinaryNodeInterface<T> leftChild = nextNode.getLeftChild();
				BinaryNodeInterface<T> rightChild = nextNode.getRightChild();
				
				// add to queue in order of recursive calls
				if (leftChild != null)
					nodeQueue.enqueue(leftChild);

				if (rightChild != null)
					nodeQueue.enqueue(rightChild);
			}
			else
			{
				throw new NoSuchElementException();
			}
		
			return nextNode.getData();
		} // end next
	
		public void remove()
		{
			throw new UnsupportedOperationException();
		} // end remove
	} // end LevelOrderIterator
} // end BinaryTree


This post has been edited by Ronald91: 20 April 2011 - 10:30 AM

Was This Post Helpful? 1
  • +
  • -

#14 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: Save The Trees Challenge

Posted 20 April 2011 - 10:54 AM

Neat! You even provide an Iterator as well!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1