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
    Gox
    Gox is offline
    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
    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
    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
    Gox
    Gox is offline
    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
    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
    •