String to Binary Tree and vice versa

Hello almighty Java gurus,

I have a little task and I have no thoughts at all anymore. I must convert a string ( like A(B,C) or A(B(C,D), E(F)) ) that represents a left-representation of binary tree. I must convert into a object and after that turn it around - I must make a right-representation of a string from object.

I made a class below:


import java.util.*;

public class kodutoo_5 implements Enumeration<kodutoo_5> {
	private String name;
	private kodutoo_5 firstChild;
	private kodutoo_5 nextSibling;
	
	kodutoo_5(String n, kodutoo_5 d, kodutoo_5 r) {
		setName(n);
		setNextSibling(d);
		setFirstChild(r);
	}
	
	kodutoo_5() {
		this("", null, null);
	}
	
	kodutoo_5(String n) {
		this(n, null, null);
	}
	
	public String getName() {
		return name;
	}
	
	public void setName(String name) {
		this.name = name;
	}
	
	public kodutoo_5 getFirstChild() {
		return firstChild;
	}
	
	public void setFirstChild(kodutoo_5 firstChild) {
		this.firstChild = firstChild;
	}
	
	public kodutoo_5 getNextSibling() {
		return nextSibling;
	}
	
	public void setNextSibling(kodutoo_5 nextSibling) {
		this.nextSibling = nextSibling;
	}
	
	public String toString() {
		return getName();
	}
	
	public boolean hasMoreElements() {
		return (getNextSibling() != null);
	}
	
	public kodutoo_5 nextElement() {
		return getNextSibling();
	}
	
	public Enumeration<kodutoo_5> child() {
		return getFirstChild();
	}
	
	private static kodutoo_5 addChild(kodutoo_5 parent, kodutoo_5 current, String nodeString) {
		kodutoo_5 result = current;
		
		//kui alluvaid ei ole, siis jarelikult juurtipp
		if(parent.getFirstChild() == null) {
			//lisame alluva
			parent.setFirstChild(new kodutoo_5(nodeString));
			result = parent.getFirstChild();
		//alluvaid on
		} else {
			result.setNextSibling(new kodutoo_5(nodeString));
			result = result.getNextSibling();
		}
		
		return result;
	}
	
	public static kodutoo_5 parseTree(String s) {
		kodutoo_5 emptyRoot = new kodutoo_5();
		parseTree(emptyRoot, s, 0);
		
		return emptyRoot.getFirstChild();
	}
	
	private static int parseTree(kodutoo_5 parent, String s, int position) {
		kodutoo_5 current = null;
        StringBuilder nodeVal = new StringBuilder();
        
        //alustame string parsimist
        for (int i = position; i < s.length(); i++) {
        	//kui leiame '('
        	if (s.charAt(i) == '(') {
        		if (nodeVal.length() > 0) {
        			current = addChild(parent, current, nodeVal.toString());
        			nodeVal = new StringBuilder();
        		}
        		
        		i = parseTree(current, s, i + 1);
        	//kui leiame ')'
        	} else if (s.charAt(i) == ')') {
        		if (nodeVal.length() > 0) {
        			current = addChild(parent, current, nodeVal.toString());
        			nodeVal = new StringBuilder();
        		}
                        
        		return i;
        	//kui leiame ','
        	} else if (s.charAt(i) == ',') {
        		if (nodeVal.length() > 0) {
        			current = addChild(parent, current, nodeVal.toString());
        			nodeVal = new StringBuilder();
        		}
        	//kui on elemendi sisu
        	} else {
        		nodeVal.append(s.charAt(i));
        	}
        }
        
        if (nodeVal.length() > 0) {
        	current = addChild(parent, current, nodeVal.toString());
        }
        
        return s.length();
	}
	
	public String rightParentheticRepresentation() {
		StringBuilder sb = new StringBuilder();
		
		//kontrollime kas juurtipp eksisteerib
		if (getName() == null) {
			throw new NullPointerException("Puud ei eksisteeri!");
		}
		
		//kontrollime ega juurtipp tuhi ei ole
		if (getName() == "") {
			throw new RuntimeException("Puud ei eksisteeri!");
		}
		
		//juurtipp eksisteerib, jarelikult ka puu
		if (getFirstChild() != null) {
			sb.append("(");
			sb.append(getFirstChild().rightParentheticRepresentation());
			Enumeration<kodutoo_5> child = child();
			
			while (child.hasMoreElements()) {
				sb.append(",");
				child = child.nextElement();
				sb.append(((kodutoo_5) child).rightParentheticRepresentation());
			}
			
			sb.append(")");
		}
		
		sb.append(getName());
		
		return sb.toString();
	}
	   
	public static void main(String[] args) {
		String s1 = "A(B,C)";
		String s2 = "A(B(C,D),E(F))";
		
		kodutoo_5 t1 = kodutoo_5.parseTree(s1);
		kodutoo_5 t2 = kodutoo_5.parseTree(s2);
		
		String v1 = t1.rightParentheticRepresentation();
		String v2 = t2.rightParentheticRepresentation();
		
		System.out.println(s1 + " ==> " + v1);
		System.out.println(s2 + " ==> " + v2);
	}
}

It work’s like a charm, but my teacher won’t accept this, because he’s wants to see that I’m using StringTokenizer class in parseTree method. So I started to rebuild my class and ended up here:


import java.util.*;

public class kodutoo_5 implements Enumeration<kodutoo_5> {
	private String name;
	private kodutoo_5 firstChild;
	private kodutoo_5 nextSibling;
	
	kodutoo_5(String n, kodutoo_5 d, kodutoo_5 r) {
		setName(n);
		setNextSibling(d);
		setFirstChild(r);
	}
	
	kodutoo_5() {
		this("", null, null);
	}
	
	kodutoo_5(String n) {
		this(n, null, null);
	}
	
	public String getName() {
		return name;
	}
	
	public void setName(String name) {
		this.name = name;
	}
	
	public kodutoo_5 getFirstChild() {
		return firstChild;
	}
	
	public void setFirstChild(kodutoo_5 firstChild) {
		this.firstChild = firstChild;
	}
	
	public kodutoo_5 getNextSibling() {
		return nextSibling;
	}
	
	public void setNextSibling(kodutoo_5 nextSibling) {
		this.nextSibling = nextSibling;
	}
	
	public String toString() {
		return getName();
	}
	
	public boolean hasMoreElements() {
		return (getNextSibling() != null);
	}
	
	public kodutoo_5 nextElement() {
		return getNextSibling();
	}
	
	public Enumeration<kodutoo_5> child() {
		return getFirstChild();
	}
	
	private static kodutoo_5 addChild(kodutoo_5 parent, kodutoo_5 current, String nodeString) {
		kodutoo_5 result = current;
		
		//kui alluvaid ei ole, siis jarelikult juurtipp
		if(parent.getFirstChild() == null) {
			//lisame alluva
			parent.setFirstChild(new kodutoo_5(nodeString));
			result = parent.getFirstChild();
		//alluvaid on
		} else {
			result.setNextSibling(new kodutoo_5(nodeString));
			result = result.getNextSibling();
		}
		
		return result;
	}
	
	public static kodutoo_5 parseTree(String s) {
		kodutoo_5 emptyRoot = new kodutoo_5();
		parseTree(emptyRoot, s);
		
		return emptyRoot.getFirstChild();
	}
	
	private static void parseTree(kodutoo_5 parent, String s) {
		
		kodutoo_5 current = null;
		StringTokenizer st = new StringTokenizer(s, "(),", true);
		StringBuilder sb = new StringBuilder();
		
		
		while(st.hasMoreTokens()) {
			String element = st.nextToken();
			if(element.compareTo("(") == 0) {
				if(sb.length() > 0) {
					current = addChild(parent, current, sb.toString());
					sb = new StringBuilder();
				}
			} else if(element.compareTo(")") == 0) {
				if(sb.length() > 0) {
					current = addChild(parent, current, sb.toString());
					sb = new StringBuilder();
				}
			} else if(element.compareTo(",") == 0) {
				if(sb.length() > 0) {
					current = addChild(parent, current, sb.toString());
					sb = new StringBuilder();
				}
			} else {
				sb.append(element);
			}
		}
		
		if(sb.length() > 0) {
			current = addChild(parent, current, sb.toString());
		}
	}
	
	public String rightParentheticRepresentation() {
		StringBuilder sb = new StringBuilder();
		
		//kontrollime kas juurtipp eksisteerib
		if (getName() == null) {
			throw new NullPointerException("Puud ei eksisteeri!");
		}
		
		//kontrollime ega juurtipp tuhi ei ole
		if (getName() == "") {
			throw new RuntimeException("Puud ei eksisteeri!");
		}
		
		//juurtipp eksisteerib, jarelikult ka puu
		if (getFirstChild() != null) {
			sb.append("(");
			sb.append(getFirstChild().rightParentheticRepresentation());
			Enumeration<kodutoo_5> child = child();
			
			while (child.hasMoreElements()) {
				sb.append(",");
				child = child.nextElement();
				sb.append(((kodutoo_5) child).rightParentheticRepresentation());
			}
			
			sb.append(")");
		}
		
		sb.append(getName());
		
		return sb.toString();
	}
	   
	public static void main(String[] args) {
		String s1 = "A(B,C)";
		//String s2 = "A(B(C,D),E(F))";
		
		kodutoo_5 t1 = kodutoo_5.parseTree(s1);
		//kodutoo_5 t2 = kodutoo_5.parseTree(s2);
		
		String v1 = t1.rightParentheticRepresentation();
		//String v2 = t2.rightParentheticRepresentation();
		
		System.out.println(s1 + " ==> " + v1);
		//System.out.println(s2 + " ==> " + v2);
	}
}

But I can’t make it right. Can anybody help me out to make this code work, please?

anyone?

I’m afraid this isn’t CS301. For people like us, we google “Binary Implementation Java” and call it a day. Your best bet is to ask your classmates. I’m glad I’ve forgotten all that to make rooms for more useful and practical stuff. I even remember tutoring at Computer Science Help Center…ah~~ those memories.

Good point. I think one of the problems is that when I’m new to something I might not even know what it’s called. So I don’t know what words to search for let alone craft a suitable search phrase that will get me good results.

I did take a look at trying to parse that string A(B,C(D,E)) or whatever it was using a StringTokenize and said… ‘er… f-that.’

I had no idea on how to even give reasonable advice on moving forward. Sorry.