10 Replies - 1832 Views - Last Post: 27 June 2011 - 10:57 AM Rate Topic: -----

#1 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

toString method

Posted 26 June 2011 - 07:38 PM

I need some help with the logic in my toString method in my SizeBSTN class, which affects the way stuff is printed out in my SizeBST class.

I thought about this for awhile and I can't think of any other way of doing.

I get after running SizeBST:
empty: (null)
([[null 35,2 null] 40,3 [null 45,1 null]])

which is not what I want. Can some give me some suggestions on approaching this problem. This is to model off a Binary Tree Model. Thanks.

public class SizeBSTN {
	SizeBSTN LSubtree;  // left subtree of this tree (may be null)
	SizeBSTN RSubtree;  // right subtree of this tree (may be null)
	int data; // data at this node of the tree
	int size; // number of tree entries that are less than or equal to data

/**
 * create a new leaf of the tree with the given data
 * @param data
 */
	public SizeBSTN(int data){
		LSubtree = null;
		RSubtree = null;
		this.data = data;
		size = 1;
	}
	
.......
	/** 
	 * see assignment for proper format for toString
	 * The format is as follows: [ LSubTree data, size Rsubtree ]. 
	 * E.g., a tree that contained only the top 3 nodes of the tree drawn above
	 * would result in the string [[null 20,1 null] 40, 2 [null 60, 1 null]]. 
	 * (Note that sizes have been updated for the smaller tree.)
	 * 
	 */
	public String toString(){
		String Ltree = "";
		String Rtree = "";
		String root = "";
		
		String temp1 = "";
		String temp2 = "";
		String temp3 = "";
		String temp4 = "";
		
		if (LSubtree != null){
			if (LSubtree.LSubtree != null){
				temp1 = LSubtree.LSubtree.toString();
			}
			else
				temp1 = "null";
			
			if (LSubtree.RSubtree != null){
				temp2 = LSubtree.RSubtree.toString();
			}
			else
				temp2 = "null";
			Ltree = "["  + temp1 + " " + LSubtree.data + "," + LSubtree.size + " " + temp2 + "]";
		}
		else
			Ltree = null;
		
		if (RSubtree != null){
			if (RSubtree.LSubtree != null){
				temp3 = RSubtree.LSubtree.toString();
			}
			else
				temp3 = "null";
			
			if (RSubtree.RSubtree != null){
				temp4 = RSubtree.RSubtree.toString();
			}
			else
				temp4 = "null";
			Rtree = "[" + temp3 + " " + RSubtree.data + "," + RSubtree.size + " " + temp4 + "]";
		}
		else
			Rtree = null;
		root = "[" + Ltree + " " + this.data + "," + this.size + " " + Rtree + "]"; 
		
		return root;

		
	}



public class SizeBST {
	SizeBSTN rootNode;

	public SizeBST(SizeBSTN root){
		rootNode =  root;
	}
	
	public String toString(){
		if (rootNode == null)
			return "(null)";
		else {
			return "("+ rootNode.toString() + ")";
		}
	}
......................
public static void main(String args []){
		SizeBST tree1 = new SizeBST(null);
		System.out.println("empty: "+tree1);
		tree1.insert(40);
		tree1.insert(35);
		tree1.insert(45);
		tree1.insert(32);
		System.out.println(tree1);
	



Is This A Good Question/Topic? 0
  • +

Replies To: toString method

#2 n8wxs   User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: toString method

Posted 27 June 2011 - 12:19 AM

Please post the insert() method code.
Was This Post Helpful? 0
  • +
  • -

#3 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 05:08 AM

	/**
	 * insert newData into tree;  if already there, do not change tree
	 * @param newData int to insert
	 */
	public void insert(int newData){
		
		SizeBSTN newNode = new SizeBSTN(newData);
		SizeBSTN current = rootNode;
		
		if (rootNode == null){
			rootNode = newNode;
		}
		else{
			while(current != null){
				// increase size for rootNode regardless because newData < rootNode.data
				
				// comparing current constantly with newData
				int d = 0;
				if (current.data > newData){
					d = 1;
				}
				else if (current.data < newData){
					d = -1;
				}
				else
					d = 0;
				
				if (d == 1){
					if (current.LSubtree == null){
						current.LSubtree = newNode;
					}
					else{
						
						current = current.LSubtree;
						break;
					}
				}
				else if (d == -1){
					if (current.RSubtree == null){
						current.RSubtree = newNode;
					}
					else{
						current = current.RSubtree;
						break;
					}
				}	
			}
		}
	}			




eclipse is actually giving me this:
empty: (null)
([[null 35,1 null] 40,1 [null 45,1 null]])

size number gets increased if there is an LSubtree for a node.
Was This Post Helpful? 0
  • +
  • -

#4 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 05:14 AM

thanks for the help
Was This Post Helpful? 0
  • +
  • -

#5 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 07:14 AM

i went through the method for insertion and it looks ok.....maybe

but my toString method is not working
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11225
  • View blog
  • Posts: 19,245
  • Joined: 19-March 11

Re: toString method

Posted 27 June 2011 - 09:58 AM

I see you're doing a recursive descent, this is the correct approach. However, it looks like it's getting too complicated.

Suppose you have nodes A, B, C, D, E, F where B and C are children of A and D and E are children of B and F is child of C. Presumably you want something like A [B [D E] C [F]]
(I'm not sure exactly how this should look - feel free to correct that)

Now: what should happen when you call A.toString?

I think it should do something like this:
1) append the name of the node and a space
2) if there is a left child or a right child, append a bracket and set a flag
3) if there is a left subTree, append leftSubtree.toString()
4) if there is a right subTree, append rightSubtree.toString()
5) if the flag is set, append a closing bracket

If you want the whole thing to be surrounded by brackets, it's probably simplest to have toString just return
"[" + printNode() + "]", where printNode is your recursive method as above.
Was This Post Helpful? 1
  • +
  • -

#7 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 10:18 AM

I see you're doing a recursive descent, this is the correct approach. However, it looks like it's getting too complicated. 

Suppose you have nodes A, B, C, D, E, F where B and C are children of A and D and E are children of B and F is child of C. Presumably you want something like A [B [D E] C [F]]
(I'm not sure exactly how this should look - feel free to correct that)

Now: what should happen when you call A.toString?

I think it should do something like this:
1) append the name of the node and a space
2) if there is a left child or a right child, append a bracket and set a flag
3) if there is a left subTree, append leftSubtree.toString()
4) if there is a right subTree, append rightSubtree.toString()
5) if the flag is set, append a closing bracket

If you want the whole thing to be surrounded by brackets, it's probably simplest to have toString just return
"[" + printNode() + "]", where printNode is your recursive method as above. 



@jon.kiparsky

hey! thanks for responding. I understand your point theortically, but I don't understand how to do that. can you be a little bit more specific? I cannot implement a printNode() method. I can only do a toString method.

the structure is [LSubtree Root,size RSubtree]

/** 
	 * see assignment for proper format for toString
	 * The format is as follows: [ LSubTree data, size Rsubtree ]. 
	 * E.g., a tree that contained only the top 3 nodes of the tree drawn above
	 * would result in the string [[null 20,1 null] 40, 2 [null 60, 1 null]]. 
	 * (Note that sizes have been updated for the smaller tree.)
	 * 
	 */
	public String toString(){
		String Ltree = "";
		String Rtree = "";
		String root = "";
		
		String temp1 = "";
		String temp2 = "";
		String temp3 = "";
		String temp4 = "";
		
		if (LSubtree != null){ 
			if (LSubtree.LSubtree != null){
				temp1 = LSubtree.LSubtree.toString();
			}
			else if(LSubtree.LSubtree == null)
				temp1 = "null";
			
			if (LSubtree.RSubtree != null){
				temp2 = LSubtree.RSubtree.toString();
			}
			else if (LSubtree.RSubtree == null)
				temp2 = "null";
		}
		else if (LSubtree == null) {
			if (RSubtree == null)
				temp1 = "[" + null + " " + LSubtree.data + "," + LSubtree.size + " " + null + "]";

			else
				temp1 = "[" + null + " " + LSubtree.data + "," + LSubtree.size + " " + RSubtree.toString() + "]";
		}
		
		Ltree = "["  + temp1 + " " + LSubtree.data + "," + LSubtree.size + " " + temp2 + "]";

		if (RSubtree != null){
			if (RSubtree.LSubtree != null){
				temp3 = RSubtree.LSubtree.toString();
			}
			else
				temp3 = "null";
			
			if (RSubtree.RSubtree != null){
				temp4 = RSubtree.RSubtree.toString();
			}
			else
				temp4 = "null";
			Rtree = "[" + temp3 + " " + RSubtree.data + "," + RSubtree.size + " " + temp4 + "]";
		}
		else
			Rtree = null;
		
		root = "[" + Ltree + " " + this.data + "," + this.size + " " + Rtree + "]"; 
		
		return root;


Was This Post Helpful? 0
  • +
  • -

#8 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 10:23 AM

i thought that by separating the Ltree, Rtree, and root would work best.
Then I recursive make the Ltree string, and similarly for Rtree.
I felt that what i did above would cover all of the situations.

I don't know how else to approach this problem. Maybe I shouldn't have separated the Ltree and Rtree.
I am not sure what you mean, @ jon.kiparsky
sorry.
Was This Post Helpful? 0
  • +
  • -

#9 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 10:39 AM

	public String toString(){
		String Ltree = "";
		String Rtree = "";
		String root = "";

		
		if (LSubtree != null){ 
			Ltree = "[" + LSubtree.toString() + "]";
		}
		
		if (RSubtree != null){
			Rtree = "[" + RSubtree.toString() + "]";
		}
		root = "[" + Ltree + "]" + " " + data + "," + size + " " + "["+ Rtree + "]";

		return root;
		
		
	}


Now,
I am doing something like this, and now I am getting this.:

empty: (null)
([[[[[] 32,1 []]] 35,1 []]] 40,1 [[[] 45,1 []]])


Was This Post Helpful? 0
  • +
  • -

#10 velo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 26-June 11

Re: toString method

Posted 27 June 2011 - 10:46 AM

i got it!! yes. thanks.

public String toString(){
		String Ltree = "";
		String Rtree = "";
		String root = "";

		
		if (LSubtree != null){ 
			Ltree =  LSubtree.toString();
		}
		else
			Ltree = null;
		
		if (RSubtree != null){
			Rtree = RSubtree.toString();
		}
		else
			Rtree = null;
		
		root = "[" + Ltree + " " + data + "," + size + " " + Rtree + "]";

		return root;
		


Was This Post Helpful? 1
  • +
  • -

#11 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11225
  • View blog
  • Posts: 19,245
  • Joined: 19-March 11

Re: toString method

Posted 27 June 2011 - 10:57 AM

Excellent. As a rule, recursive methods should be simple - that's the point. If there's a lot of iffing and elseing, then you probably need to reconsider your approach. This looks a lot better.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1