# QuadTree insertion based on string

• October 23rd, 2012, 10:38 PM
lucasfeijo
There's this string containing B, W and G (standing for black, white and gray). It defines the pre-ordered path of the quadtree I want to build. I wrote this method for filling the QuadTree class I also wrote but it doesn't work, it inserts correctly until it reaches a point in the algorithm it needs to "return".

I use math quadrants convention order for insertion, such as northeast, northwest, southwest and southeast.
A quadtree has all it's leafs black or white and all the other nodes gray

The node used in the tree is called Node4T and has a char as data and 4 references to other nodes like itself, called, respectively NE, NW, SW, SE.

Code :

``` public void insert(char val) { if(root==null) { root = new Node4T(val); } else { insert(root, val); } }   public void insert(Node4T n, char c) { if(n.data=='G') // possible to insert { if(n.NE==null) { n.NE = new Node4T(c); return; } else { insert(n.NE,c); } if(n.NW==null) { n.NW = new Node4T(c); return; } else { insert(n.NW,c); } if(n.SW==null) { n.SW = new Node4T(c); return; } else { insert(n.SW,c); } if(n.SE==null) { n.SE = new Node4T(c); return; } else { insert(n.SE,c); } } else // impossible to insert {   } }```

The input "GWGGWBWBGBWBWGWBWBWGGWBWBWGWBWBGBWBWGWWWB" is given a char at a time to the insert method and then the print method is called, pre-ordered, and the result is "GWGGWBWBWBWGWBWBW".

How do I make it import the string correctly? Ignore the string reading process, suppose the method is called and it has to do it's job.

Obs: for those who don't know what is a Quad Tree, it is a data structure that's usually used for storing images. Example: http://upload.wikimedia.org/wikipedi...bitmap.svg.png