Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 6 of 6
  1. #1
    New to the CF scene
    Join Date
    Apr 2011
    Location
    Ireland
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Unhappy Simple String binary tree implementation help

    Hi,
    I'm trying to implement a binary tree with letters but am having no joy seting up the tree. I need the letters in a particular order as when searching the tree they will be encoded to morse code using their path.
    This seemed to work fine until I wrapped the addleft/right statements inthe init() method.
    Code:
    package gmit;
    
    import java.util.*;
    public class Node {
    	public Node parent;
    	public Node left;
    	public Node right;
    	public Item item;
    	public Item getItem() {
    		return item;
    	}
    
    	public void setItem(Item item) {
    		this.item = item;
    	}
    
    	private List<Node> children = new ArrayList<Node>();
    	private String letter;
    	
    	public Node(){
    	}
    	
    	public Node(String letter){
    		this.letter = letter;
    	}
    	public void left(Node left){
    		this.setLeft(left);
    	}
    	
    	public void right(Node right){
    		this.setRight(right);
    	}
    	
    	public boolean isRoot(){
    		return this.parent == null;
    	}
    	
    	public boolean hasChildren(){
    		return this.children.size() > 0;
    	}
    	
    	public void addChild(Node child){
    		child.setParent(this);
    		children.add(child);
    	}
    	
    	public void removeChild(Node child){
    		children.remove(child);
    	}
    	
    	public Node getParent(){
    		return this.parent;
    	}
    	
    	public void setParent(Node parent){
    		this.parent = parent;
    	}
    	
    	public Node[] children(){
    		return (Node[]) children.toArray(new Node[children.size()]);
    	}
    
    	public void setLeft(Node left) {
    		this.left = left;
    	}
    
    	public Node getLeft() {
    		return left;
    	}
    
    	public void setRight(Node right) {
    		this.right = right;
    	}
    
    	public Node getRight() {
    		return right;
    	}
    }
    I am probably going the complete wrong way about this but any direction would be much appreciated. Can not get my head round any of the examples or tutorials I've seen
    Code:
    package gmit;
    
    import java.util.*;
    
    public class BinaryTree {
    
    	public BinaryTree(){
    		Node root= new Node();
    		root="start";
    		init(root);
    	}
    
    	private void init(Node root){
    		//define root
    		Node t="t";
    		//set right side of tree
    		root.addright(t);
    		t.addright(m)="m";
    		t.addleft(n)="n";
    		n.addleft(d)="d";
    		n.addright(k)="k";
    		m.addleft(g)="g";
    		m.addright(o)="o";
    		d.addleft(b)="b";
    		d.addright(x)="x";
    		k.addleft(c)="c";
    		k.addright(y)="y";
    		g.addleft(z)="z";
    		g.addright(q)="q";
    		o.addleft(o2)="-";
    		o.addright(ch)="-";
    		b.addleft(6)="6";
    		z.adleft(7)="7";
    		o2.adleft(8)="8";
    		ch.addleft(9)="9";
    		ch.addright(0)="0";
    
    		//set left side of tree
    		root.addleft(e)="e";
    		e.addleft(i)="i";
    		e.addright(a)="a";
    		i.addleft(s)="s";
    		i.addright(u)="u";
    		a.addleft(r)="r";
    		a.addright(w)="w";
    		s.addeft(h)="h";
    		s.addright(v)="v";
    		u.addleft(f)="f";
    		u.addright(u2)="-";
    		r.addleft(l)="l";
    		r.addriht(a2)="-";
    		w.addleft(p)="p";
    		w.addright(j)="j";
    		n.addleft(5)="5";
    		n.addleft(4)="4";
    		v.addright(3)="3";
    		u.addright(2)="2";
    		j.addright(1)="1";
    	}
    	public static void main(String[] args){
    		new BinaryTree();
    	}
    }

  2. #2
    Regular Coder Gox's Avatar
    Join Date
    May 2006
    Location
    Ontario, Canada
    Posts
    392
    Thanks
    2
    Thanked 20 Times in 20 Posts
    Could you specify what the exact issue is? A quick look at the code makes me wonder if it even compiles.

    Code:
    Node t="t";
    Is it possible to assign a String to a Node?

    Code:
    root.addright(t);
    I don't see an addright() method in the Node class you posted

    Code:
    n.addleft(d)="d";
    Where is node N declared?
    I don't see an addleft() method in the Node class you posted
    If there is an addleft method does it return something that you can assign the String "d" to?

    etc. etc.

  3. #3
    New to the CF scene
    Join Date
    Apr 2011
    Location
    Ireland
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts
    No it doesn't compile. I have changed the node assignment to
    Code:
    root.setRight(new Node("t"));
    as set in my Node class.but how then do I set the children of that node.
    Sorry for my ignorance but its very frustrating.

  4. #4
    New to the CF scene
    Join Date
    Apr 2011
    Location
    Ireland
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ok so I've changed the node implementation
    Code:
    package gmit;
    
    public class BinaryTree {
    
    	public BinaryTree(){
    		Node root= new Node();
    		Item start=null;
    		root.setItem(start);
    		//dfs(root, 0);
    		init(root);
    	}
    
    	private void init(Node root){
    		//assign right nodes
    		Node t=new Node("t");
    		Node m=new Node("m");
    		Node o=new Node("o");
    		Node o2=new Node("");
    		Node ch=new Node("ch");
    		Node zero=new Node("0");
    		Node n=new Node("n");
    		Node d=new Node("d");
    		Node k=new Node("k");
    		Node g=new Node("g");
    		Node b=new Node("b");
    		Node x=new Node("x");
    		Node c=new Node("c");
    		Node y=new Node("y");
    		Node z=new Node("z");
    		Node q=new Node("q");
    		Node six=new Node("6");
    		Node sev=new Node("7");
    		Node eight=new Node("8");
    		Node nine=new Node("9");
    		
    		//assign left nodes
    		Node e = new Node("e");
    		Node i = new Node("i");
    		Node a = new Node("a");
    		Node s = new Node("s");
    		Node u = new Node("u");
    		Node r = new Node("r");
    		Node w = new Node("w");
    		Node h = new Node("h");
    		Node v = new Node("v");
    		Node f = new Node("f");
    		Node u2 = new Node("");
    		Node l = new Node("l");
    		Node a2 = new Node("");
    		Node p = new Node("p");
    		Node j = new Node("j");
    		Node five = new Node("5");
    		Node four = new Node("4");
    		Node three = new Node("3");
    		Node two = new Node("2");
    		Node one = new Node("1");
    		
    		//set right side of tree
    		root.setRight(t);
    		t.setRight(m);
    		t.setLeft(n);
    		n.setLeft(d);
    		n.setRight(k);
    		m.setLeft(g);
    		m.setRight(o);
    		d.setLeft(b);
    		d.setRight(x);
    		k.setLeft(c);
    		k.setRight(y);
    		g.setLeft(z);
    		g.setRight(q);
    		o.setLeft(o2);
    		o.setRight(ch);
    		b.setLeft(six);
    		z.setLeft(sev);
    		o2.setLeft(eight);
    		ch.setLeft(nine);
    		ch.setRight(zero);
    		
    		//set left side of tree
    		root.setLeft(e);
    		e.setLeft(i);
    		e.setRight(a);
    		i.setLeft(s);
    		i.setRight(u);
    		a.setLeft(r);
    		a.setRight(w);
    		s.setLeft(h);
    		s.setRight(v);
    		u.setLeft(f);
    		u.setRight(u2);
    		r.setLeft(l);
    		r.setRight(a2);
    		w.setLeft(p);
    		w.setRight(j);
    		h.setLeft(five);
    		h.setRight(four);
    		v.setRight(three);
    		u2.setLeft(two);
    		j.setRight(one);
    		
    	}
    	
    	private void dfs(Node node, int index){ //A recursive depth first search
    		for (int i = 1; i <= index; i++) System.out.print("\t"); //The parameter index is used to tab each level of the tree
    		System.out.println(node.getItem().process()); //Process the node
    		
    		Node[] children = node.children(); //Get the child nodes
    		for (int i = 0; i < children.length; i++) {
    			Node next = children[i]; //Get the next child node
    			dfs(next, index + 1); //Recursive method call. Adds method call to the top of the JVM method stack
    		}
    		
    	}
    	
    	public static void main(String[] args){
    		new BinaryTree();
    	}
    }
    so my code compiles but it won't print out now. any suggestions?

  5. #5
    Regular Coder Gox's Avatar
    Join Date
    May 2006
    Location
    Ontario, Canada
    Posts
    392
    Thanks
    2
    Thanked 20 Times in 20 Posts
    Looks like you have a dfs method to print out the tree, but it doesn't seem like you ever call it.

  6. #6
    New to the CF scene
    Join Date
    Apr 2011
    Location
    Ireland
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts
    If I call it
    Code:
    dfs(root,0);
    I get a null pointer exception but am not sure why


 

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •