0

In solving this problem: http://www.cs.duke.edu/csed/newapt/drawtree.html I wrote the code below but it seems to run too slow. Is there a faster way of checking all of the child nodes w/o using a FOR loop? Would a queue be helpful? 

public class DrawTree {
    HashMap<String, ArrayList<String>> map = 
            new HashMap<String, ArrayList<String>>();
    ArrayList<String> drawing = new ArrayList<String>(); 
    String root;
    public String[] draw(int[] parents, String[] names) {


         for(int x=0; x<parents.length; x++)
         {
             int parentindex = parents[x];
             //root name

             if(parentindex==-1)
            {
                 root=names[x];
                 if(!map.containsKey(names[x]))
                 {

                     map.put(names[x], new ArrayList<String>()); 
                 }

                 continue;
            }

             //add parent, child to map
             if (!map.containsKey(names[parentindex])) 
                             map.put(names[parentindex], 
                                     new ArrayList<String>());
             map.get(names[parentindex]).add(names[x]);
         }


         sketch("",root,false);
        return drawing.toArray(new String[drawing.size()]);
      }
    //***IMPROVE RUN TIME - different algorithm??***
     //method takes root and prefix?
     public void sketch(String parent, String child, boolean addPipe){

         StringBuilder toAdd = new StringBuilder();


         //don't need to add connector pipe
         if(!addPipe)
         {
            //number of spaces to add to prefix
            int spaces = parent.indexOf('-')+1;

             //add spaces to prefix
            while(spaces>0)
            {
                toAdd.append(" ");
                spaces--;
            }
            toAdd.append("+-"+child);
         }


         //index of pipe in parent, -1 if parent doesn't have pipe
         int parentPipe = parent.indexOf('|');

        //need to add connector pipe & parent has pipe 
            // (is a child of a subtree)
         if(parentPipe>0)
         {
            //number of spaces to add to prefix
             int spaces = parent.indexOf('-')+1;

             //add spaces to prefix
             while(spaces>0)
             {
                 if(spaces==parentPipe) toAdd.append('|');
                 else toAdd.append(" ");
                 spaces--;
             }
             toAdd.append("+-"+child);   

         }

         //need to add pipe and parent doesn't have pipe
         if(addPipe && parentPipe<0)
         {
             int spaces = parent.indexOf('-')+1;
             while(spaces>0)
             {
                 if(spaces==2) toAdd.append('|');
                 else toAdd.append(" ");
             }
             toAdd.append("+-"+child);   
         }

         //add child to list of tree drawing
         String node = toAdd.toString();
         drawing.add(node);
         //System.out.println(node);     

         //loop through list of children, passing each recursively
             //...count level?
         if(map.containsKey(child))
         {
             //System.out.println("map works");
             for(int x = 0; x<map.get(child).size(); x++)
             {
                 boolean pipe = false;
                 if(x<(map.get(child).size()-1)) pipe=true;
                 //System.out.println(map.get(child).get(x));
                 sketch(node, map.get(child).get(x), pipe);
             } 
         }

     }
4

1 回答 1

0

在这种情况下，我认为队列不会有帮助。For循环可能是这样做的方式

public class DrawTree {
    public String[] lines;
    public int lineNum;

    public String[] draw(int[] parents, String[] names) {
        lines = new String[parents.length];
        lineNum = 0;
        drawLeaf(parents, names, -1, 0);
        return lines;
    }

    public void drawLeaf(int[] parents, String[] names, int root, int depth) {
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == root) {
                lines[lineNum] = "";
                for (int j = 0; j < depth; j++) {
                    lines[lineNum] += "  ";
                }

                lines[lineNum] += "+-" + names[i];
                int pipeNum = lineNum - 1;
                while ((pipeNum >= 0)
                        && (lines[pipeNum].charAt(depth * 2) == ' ')) {
                    String oldLeaf = lines[pipeNum];
                    lines[pipeNum] = "";
                    for (int j = 0; j < oldLeaf.length(); j++) {
                        if (j == depth * 2) {
                            lines[pipeNum] += '|';
                        } else {
                            lines[pipeNum] += oldLeaf.charAt(j);
                        }
                    }
                    pipeNum--;
                }

                lineNum++;
                drawLeaf(parents, names, i, 1 + depth);
            }
        }
    }
}
于 2012-09-03T08:24:05.007 回答