JAVA BINARY TREE & NODE DATA STRUCTURE

Posts

Pages: 1
supremewarrior
70
02/22/2012 02:35 PM
This is my first time ever implementing any binary tree or node data structure and I'm unsure whether I'm doing it correctly or not. Could someone who is experienced with binary trees and nodes tell me if anything is wrong with my classes? I want be able to use these draw the tree visually in real time.

Also I'm having trouble implementing the attach(t1, t2) method for attaching a subtree to the tree.

Show



import javax.swing.JOptionPane;

public class Tree{
	Node root = null;
	Node leftNode = null;
	Node rightNode = null;
	
	// Returns the root node
	public Node getRoot(){
		return root;
	}
	
	// Sets the root node, if the tree is empty. 
	// Otherwise adds node to the tree
	public Node addRoot(String element, Node a){
		if(root == null){
			Node r = new Node(element, a);
			root = r;
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, root node is already present", 0);
		}
		return getRoot();
	}
	
	// Checks if there is a left node, if there isn't makes Node b the new left node with element
	// as the value of the Node b. If there is a left node return an error
	public Node insertLeft(Node b, String element){
		// If there is no left node, make Node b the left node
		if(b == null){
			leftNode = new Node(element, b);
		// If there is already a left node, return an error 
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, left node is already present", 0);
		}
		return leftNode;
	}
	
	// Checks if there is a right node, if there isn't makes Node c the new right node with element
	// as the value of the Node c. If there is a right node return an error
	public Node insertRight(Node c, String element){
		// If there is no right node, make Node c the right node
		if(c == null){
			rightNode = new Node(element, c);
		// If there is already a right node, return an error 
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, right node is already present", 0);
		}
		return rightNode;
	}
	
	// Removes Node d from the tree, if Node d has any children in the left
	// or right branch of the subtree, replace the child node with Node d and
	// return Node d
	// Return an error if Node d has two child nodes.
	public void removeNode(Node d){
		if(d.getRight()==null&&d.getLeft()==null){
			d = null;
		} else if(d.getRight()!=null){
			d = d.getRight();
		} else if(d.getLeft()!=null){
			d = d.getLeft();
		} else if(d.getRight()!=null&&d.getLeft()!=null){
			JOptionPane.showMessageDialog(null, this, "Error, cannot remove a node that has two child nodes", 0);
		}
	}

	// Attaches subtree
	public void attach(){
		
	}
	
	public class Node {
		String element;
		Node nextNode;
		Node head, tail;
		int size;
		
		// Creates a node with the given element and next node
		public Node(String s, Node n){
			element = s;
			nextNode = n;
		}
		
		// Returns the right node
		public Node getRight(){
			return rightNode;
		}
		
		// Returns the left node
		public Node getLeft(){
			return leftNode;
		}
		
		// Returns the element of the node
		public String getElement(){
			return element;
		}
		
		// Returns the next node of this node
		public Node getNext(){
			return nextNode;
		}
		
		// Sets the element of this node
		public void setElement(String newElement){
			element = newElement;
		}
		
		// Sets the next node of this node
		public void setNext(Node newNext){
			nextNode = newNext;
		}
		
		// Adds the node to the last node of the list
		public void addFirst(Node first){
			first.setNext(head);		// Points to the previous head node
			head = first;				// Make the head node point to the new node
			size = size + 1;			// Increment the node count
		}
		
		// Adds the node to the last node of the list
		public void addLast(Node last){
			last.setNext(null);			// Make the new node "last" point to null
			tail.setNext(last);			// Make the old tail node point to the new tail node
			tail = last;				// Make tail node point to new node
			size = size + 1;			// Increment the node count			
		}
		
		// Removes the first node in the list. Before removing it points to the 
		// new head node then removes the old head node.
		public void removeFirst(Node v){
			if(head == null){
				System.out.println("Error, cannot remove. The list is empty");
			}
			v = head;
			head = head.getNext();
			v.setNext(null);
			size = size - 1;
		}
	}
}
[/size]
Show

EDIT: Hide tags not working...
Muninn
2233
02/22/2012 07:57 PM
Are you using Node for anything else in your program? The elements you're defining for it seem to be more in line with a Linked List than a binary tree.

As it is right now, you have no way to extend your tree (you've basically got an object which contains three linked lists instead of a tree). You'll want to make it such that either your Node item has fields for Right and Left child nodes, or make it so that the leftNode and rightNode elements of your Tree class point to subtrees instead of nodes (this would necessitate something along the lines of "Node content;" to contain the node itself).

how you implement the attach() method would depend on which solution you choose.
supremewarrior
70
02/22/2012 08:52 PM
author=Muninn
Are you using Node for anything else in your program? The elements you're defining for it seem to be more in line with a Linked List than a binary tree.

As it is right now, you have no way to extend your tree (you've basically got an object which contains three linked lists instead of a tree). You'll want to make it such that either your Node item has fields for Right and Left child nodes, or make it so that the leftNode and rightNode elements of your Tree class point to subtrees instead of nodes (this would necessitate something along the lines of "Node content;" to contain the node itself).

how you implement the attach() method would depend on which solution you choose.


import javax.swing.JOptionPane;

public class Tree{
	Node root = null;
	Node leftNode = null;
	Node rightNode = null;
	
	// Returns the root node
	public Node getRoot(){
		return root;
	}
	
	// Sets Node a as the root node, if the tree is empty. 
	// Otherwise returns an error
	public Node addRoot(String element, Node a){
		if(root == null){
			Node r = new Node(element, a);
			root = r;
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, root node is already present", 0);
		}
		return getRoot();
	}
	
	// Removes Node d from the tree, if Node d has any children in the left
	// or right branch of the subtree, replace the child node with Node d and
	// return Node d
	// Return an error if Node d has two child nodes.
	public void removeNode(Node d){
		if(d.getRight()==null&&d.getLeft()==null){
			d = null;
		} else if(d.getRight()!=null){
			d = d.getRight();
		} else if(d.getLeft()!=null){
			d = d.getLeft();
		} else if(d.getRight()!=null&&d.getLeft()!=null){
			JOptionPane.showMessageDialog(null, this, "Error, cannot remove a node that has two child nodes", 0);
		}
	}

	// Attaches subtree
	public void attach(){
		
	}
	
	public class Node {
		String element;
		Node nextNode;
		
		// Creates a node with the given element and next node
		public Node(String s, Node n){
			element = s;
			nextNode = n;
		}
		
		// Returns the right node
		public Node getRight(){
			return rightNode;
		}
		
		// Returns the left node
		public Node getLeft(){
			return leftNode;
		}
		
		// Returns the element of the node
		public String getElement(){
			return element;
		}
		
		// Returns the next node of this node
		public Node getNext(){
			return nextNode;
		}
		
		// Sets the element of this node
		public void setElement(String newElement){
			element = newElement;
		}
		
		// Checks for a left node, if there isn't makes Node b the new left node with element
		// as the value of the Node b. If there is a left node return an error
		public Node insertLeft(Node b, String element){
			// If there is no left node, make Node b the left node
			if(b == null){
				leftNode = new Node(element, b);
			// If there is already a left node, return an error 
			} else {
				JOptionPane.showMessageDialog(null, this, "Error, left node is already present", 0);
			}
			return leftNode;
		}
		
		// Checks for a right node, if there isn't makes Node c the new right node with element
		// as the value of the Node c. If there is a right node return an error
		public Node insertRight(Node c, String element){
			// If there is no right node, make Node c the right node
			if(c == null){
				rightNode = new Node(element, c);
			// If there is already a right node, return an error 
			} else {
				JOptionPane.showMessageDialog(null, this, "Error, right node is already present", 0);
			}
			return rightNode;
		}
	}
}

Is this what you mean by making Node have left and right?
Muninn
2233
02/22/2012 09:35 PM
The two methods that you moved would need to go in there, but I also meant to add something like this (only the Node code is shown, the change is a few lines in with a comment by it): 

	public class Node {

		String element;

		Node nextNode;

                Node rightNode, leftNode;             //This is the added element

		

		// Creates a node with the given element and next node

		public Node(String s, Node n){

			element = s;

			nextNode = n;

		}

		

		// Returns the right node

		public Node getRight(){

			return rightNode;

		}

		

		// Returns the left node

		public Node getLeft(){

			return leftNode;

		}

		

		// Returns the element of the node

		public String getElement(){

			return element;

		}

		

		// Returns the next node of this node

		public Node getNext(){

			return nextNode;

		}

		

		// Sets the element of this node

		public void setElement(String newElement){

			element = newElement;

		}

		

		// Checks for a left node, if there isn't makes Node b the new left node with element

		// as the value of the Node b. If there is a left node return an error

		public Node insertLeft(Node b, String element){

			// If there is no left node, make Node b the left node

			if(b == null){

				leftNode = new Node(element, b);

			// If there is already a left node, return an error 

			} else {

				JOptionPane.showMessageDialog(null, this, "Error, left node is already present", 0);

			}

			return leftNode;

		}

		

		// Checks for a right node, if there isn't makes Node c the new right node with element

		// as the value of the Node c. If there is a right node return an error

		public Node insertRight(Node c, String element){

			// If there is no right node, make Node c the right node

			if(c == null){

				rightNode = new Node(element, c);

			// If there is already a right node, return an error 

			} else {

				JOptionPane.showMessageDialog(null, this, "Error, right node is already present", 0);

			}

			return rightNode;

		}

	}

}


You'll also remove the "Node leftNode, rightNode;" from your Tree class. This will result in a "Tree" object which contains the pointer to the root node of the tree, methods for searching the tree (ie, if you're using a tree to order terms for searchability, or if you're looking to insert a term into a specific spot), while the "Node" object contains links to the other nodes in the tree, and methods for adding or subtracting elements.
supremewarrior
70
02/22/2012 10:08 PM
Ah, I see... but I thought that leftNode and rightNode would make more sense in the Tree class than in the Node class... Can you explain why I'm wrong?

This should be correct now.


import javax.swing.JOptionPane;

public class Tree{
	Node root = null;
	
	// Sets Node a as the root node, if the tree is empty. 
	// Otherwise returns an error
	public Node addRoot(String element, Node n){
		if(root == null){
			Node r = new Node(element, n);
			root = r;
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, root node is already present", 0);
		}
		return getRoot();
	}
	
	// Returns the root node
	public Node getRoot(){
		return root;
	}
	
	// Removes Node d from the tree, if Node d has any children in the left
	// or right branch of the subtree, replace the child node with Node d and
	// return Node d
	// Return an error if Node d has two child nodes.
	public void removeNode(Node n){
		if(n.getRight()==null&&n.getLeft()==null){
			n = null;
		} else if(n.getRight()!=null){
			n = n.getRight();
		} else if(n.getLeft()!=null){
			n = n.getLeft();
		} else if(n.getRight()!=null&&n.getLeft()!=null){
			JOptionPane.showMessageDialog(null, this, "Error, cannot remove a node that has two child nodes", 0);
		}
	}
	
	// Checks for a left node, if there isn't makes Node b the new left node with element
	// as the value of the Node b. If there is a left node return an error
	public Node insertLeft(Node n, String element){
		// If there is no left node, make Node b the left node
		if(n == null){
			n.leftNode = new Node(element, n);
		// If there is already a left node, return an error 
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, left node is already present", 0);
		}
		return n.leftNode;
	}
	
	// Checks for a right node, if there isn't makes Node c the new right node with element
	// as the value of the Node c. If there is a right node return an error
	public Node insertRight(Node n, String element){
		// If there is no right node, make Node c the right node
		if(n == null){
			n.rightNode = new Node(element, n);
		// If there is already a right node, return an error 
		} else {
			JOptionPane.showMessageDialog(null, this, "Error, right node is already present", 0);
		}
		return n.rightNode;
	}

	// Attaches subtree
	public void attach(){}
	
	public class Node {
		String element;
		Node nextNode;
		Node leftNode, rightNode = null;
		
		// Creates a node with the given element and next node
		public Node(String s, Node n){
			element = s;
			nextNode = n;
		}
		
		// Sets the right node
		public void setRight(Node n){
			rightNode = n;
		}
		
		// Returns the right node
		public Node getRight(){
			return rightNode;
		}

		// Sets the left node
		public void setLeft(Node n){
			leftNode = n;
		}
		
		// Returns the left node
		public Node getLeft(){
			return leftNode;
		}

		// Sets the next node of this node
		public void setNext(Node n){
			nextNode = n;
		}
		
		// Returns the next node of this node
		public Node getNext(){
			return nextNode;
		}
		
		// Sets the element of this node
		public void setElement(String newElement){
			element = newElement;
		}
		
		// Returns the element of the node
		public String getElement(){
			return element;
		}
	}
}
Muninn
2233
02/22/2012 10:30 PM
You're not wrong, it can be done either way and I just happened to go into more detail about one of them. If you put leftNode and rightNode in the Tree class, they should be "Tree leftNode, rightNode;", and you'll need to add a separate element along the lines of "Node content;". The beginning of it might look something like this: 

public class Tree

{

   Node content; //this holds the Node data structure.

                 //  If you're not doing anything else with

                 //  the nodes, you could probably just roll

                 //  them into the Tree and replace this with

                 //  "String content" (or whatever else you're storing)

   Tree parent, leftChild, rightChild;  //points to the adjacent nodes in both

                                        // directions.  parent will be null value

                                        // if this particular tree object is root.

   /* various methods would go here */

}
supremewarrior
70
02/22/2012 10:35 PM
Oh ok, I thought as much. It's just with data structures like these I tend to think that they should be done a certain way to maximize their usefulness.

Thank you for that!

Now my next question arises. How would I draw the tree visually? I'm planning to just draw the tree on a JFrame and override the default paint method with my own implementation.
Muninn
2233
02/22/2012 10:52 PM
Sorry, I can't really help with the graphical portion of that because I've not really had any experience in java graphics.
Pages: 1