Hi guys, I just can't figure out how to traverse trough this heap. It's a 4-heap and I'm trying to implement a toString method for it. It should return a string and must be recursive. Like pre-order traversal. I'm lost with it.

public String toString(int index,String out)
  {
    int child = index*4+1;
   
    out+= (array[index] +"/n"); 


   if (child<=currentSize-1)
   {
     out+=toString(child,out.concat("/t"));
   }
   
   if (child+1<=currentSize-1)
   {
     out+=toString(child+1,out.concat("/t"));
   }
   
   if (child+2<=currentSize-1)
   {
     out+=toString(child+2,out.concat("/t"));
   }
   
   if (child+3<=currentSize-1)
   {
     out+=toString(child+3,out.concat("/t"));
   }    
   return out;
  }

With this code it outputs 100% correctly but I need to return it as a single string ? Maybe some recursion guru can help me :P

public String toString(int index,String out)
  {
    int child = index*4+1; 
    System.out.println(out + array[index] +"\n");   

   
   if (child<=currentSize-1)
   {
     toString(child,out.concat("\t"));
   }
   
   if (child+1<=currentSize-1)
   {
     toString(child+1,out.concat("\t"));
   }
   
   if (child+2<=currentSize-1)
   {
     toString(child+2,out.concat("\t"));
   }
   
   if (child+3<=currentSize-1)
   {
     toString(child+3,out.concat("\t"));
   }   
   
   return out;
  }

speedy patch

java.util.List<String> lista;

    @Override
    public String toString() {
        lista = new java.util.ArrayList<String>();
        example();
        return lista.toString();
    }

    private void example() {
        for (int i = 0; i < 10; i++) {
            System.out.print(Integer.toString(i) + "\n");
            lista.add(Integer.toString(i));
        }
    }

Thanks quuba! I've found an alternative though, which is a preorder traversal of the heap. I still think it can be a little *neater*.

public String toString(int index,String out)
  {
    int child = index*4+1; 
    String carry = new String(out);
    out +=  array[index] +"\n";    
    
  
   if (child<=currentSize-1)
   {    
     out += toString(child,carry+"\t");
   }
   
   if (child+1<=currentSize-1)
   {
     out += toString(child+1,carry+("\t"));
   }
   
   if (child+2<=currentSize-1)
   {
     out += toString(child+2,carry+("\t"));
   }
   
   if (child+3<=currentSize-1)
   {
     out += toString(child+3,carry+("\t"));
   }   
   return out;   
}
This article has been dead for over six months. Start a new discussion instead.