Working with a custom General Tree... advice needed.

I have a game that uses an AI to find the fastest route from one Wikipedia page to another by cycling through links. This StorageTree does all of the logic, for the most part, and works except for one problem. Wikipedia is immense, and so recursive page loading effectively does not end until the goal is found or the timeout is reached. I'm fine with that, it's all neccessary, of course, but there is one problem:

Currently as elements are added to my tree they are added in preorder - from the leftmost childnode to the parent nodes and finally to the right nodes. The problem is that I want to add pages on a levelorder basis so that I check every link on a site before moving on to sites further away from the original root. Basically I want to add items in the order of their depths in the tree, rather than the usual recursive way to do things.

I've thought of a few ways to do this, but this obviously needs to be efficient so it can juggle the most pages at once, and the ways I was thinking of involve a lot of wasted memory. Anyone have any ideas?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

/**
 * The StorageTree is used by WikiRipper to save all possible moves
 * in an efficient and easily accessible manner. It is a basic general
 * tree with an array of nodes to each leaf. These nodes represent each
 * article, and their next nodes are all articles they are linked to. Upon
 * creation, the StorageTree constructs itself using timeout, start, and end
 * provided by the WikiRipper.
 * @author Eli Delventhal
 *
 */

import java.util.LinkedList;
import java.util.TreeSet;
import java.util.Iterator;

public class StorageTree implements java.io.Serializable
{
   private static final long serialVersionUID = 1L;
   private Node root;
   private int timeout;
   private long startTime;
   private String goal;
   private TreeSet added; //any article added already is put into this list
   private Node found; //if this node is not null then a goal has been found
   
   public StorageTree(int to, String start, String end)
   {
      //The start time is used to test when to stop loading
      startTime = new java.util.Date().getTime();
      added = new TreeSet();
      timeout = to; goal = end;
      root = new Node(start);
      addNode(root);
      clear();
   }
   
   /**
    * addNode is a recursive method to add this node to the tree, and then
    * it calls itself for each of the node's links.
    * @param n   The node to add
    */
   private void addNode(Node n)
   {
      //Halt in case of a timeout
      if (new java.util.Date().getTime() - startTime >= timeout*1000)
         return;
      //Halt in case the goal has been found
      if (n.data.equalsIgnoreCase(goal))
      {
         found = n;
         return;
      }
      //Halt if the goal has already been found
      if (found != null)
         return;
      
      //Get the links out and remove any that are already in the tree
      LinkedList l = getLinks(n.data);
      for (Iterator i = l.iterator(); i.hasNext();)
      {
         Object o = i.next();
         if (added != null)
         {
            if (added.contains(o))
               i.remove();
            else
               added.add(o);
         }
      }
      //Create an array to represent all links from this Node
      n.next = new Node[l.size()];
      
      //Cycle through every link and call addNode for each of
      //those Nodes, and also set their parent to this Node
      int index = 0;
      for (Iterator i = l.iterator(); i.hasNext(); index++)
      {
         n.next[index] = new Node((String)i.next());
         n.next[index].parent = n;
         addNode(n.next[index]);
      }
   }
   
   /**
    * Called after the search is over or the goal has been found,
    * clearing out all variables used.
    */
   private void clear()
   {
      added = null; //added is no longer needed, so clear it
      //Although this seems crazy, if a goal was found then there is
      //no reason to preserve any other parts of the tree.
      if (found != null)
         root = null;
      goal = null; //We don't need to know the goal anymore
      startTime = timeout = 0; //Clear startTime and timeout, uneeded
   }
   
   /**
    * Pull all the links out of an article and return them as a LinkedList.
    * @param article   The article on Wikipedia to load
    * @return   Every link found within that article
    */
   private LinkedList getLinks(String article)
   {
      LinkedList choices = new LinkedList();
      String page = ConnectionManager.loadPage(article);
      String search = "<a href=\"/wiki/";
      for (int i = 0; i < page.length() - search.length(); i++)
      {
         try
         {
            if (page.substring(i,i+search.length()).equals(search))
               choices.add(page.substring(i+search.length(),page.indexOf('\"',i+search.length())));
         }
         catch (Exception e) {}
      }
      return choices;
   }
   
   /**
    * Returns the absolute best choice to make, but returns null if there
    * was never any goal found with the provided timeout.
    * @param location   The location to get the best choice from.
    * @return   The article of the best choice.
    */
   public String getBestChoice(String location)
   {
      if (found == null)
         return null;
      Node search = found;
      while (search.parent != null)
      {
         if (search.parent.data.equalsIgnoreCase(location))
            return search.data;
         search = search.parent;
      }
      return null;
   }
   
   /**
    * Mostly for debug reasons, this method prints the path, from the
    * found Node upwards, of the best choice.
    */
   public void printBestChoice()
   {
      if (found == null)
      {
         System.out.println("Wasn't found... will instead print tree.");
         printTree();
         return;
      }
      Node search = found;
      while (search.parent != null)
      {
         System.out.print(search.data + " ");
         search = search.parent;
      }
      System.out.println();
   }
   
   /**
    * Prints out the entire tree in preorder.
    */
   private void printTree()
   {
      printNode(root);
   }
   
   private void printNode(Node n)
   {
      if (n == null)
         return;
      System.out.print(n.data + ": ");
      if (n.next == null)
         return;
      for (int i = 0; i < n.next.length; i++)
         printNode(n.next[i]);
      System.out.println();
   }
   
   private class Node
   {
      public Node[] next;
      public String data;
      public Node parent; //parent is neccessary to find the fastest path
      
      public Node(String d)
      {
         data = d;
      }
   }
}