BinTree


1   package ro.infoiasi.donald.compiler.simple;
2   
3   import java.util.*;
4   
5   /** A binary tree of objects */
6   public class BinTree {
7       private BinTreeNodeP root;
8   
9       /** A node in a binary tree */
10      private class BinTreeNodeP implements BinTreeNode {
11          private Object   obj;
12          private BinTreeNodeP parent;
13          private BinTreeNodeP left;
14          private BinTreeNodeP right;
15          private int weight = 1;
16  
17          BinTreeNodeP(Object   obj) {
18              this.obj = obj;
19          }
20  
21          public void put(Object   obj) {
22              this.obj = obj;
23          }
24          public Object   get() {
25              return obj;
26          }
27  
28          public BinTreeNode parent() {
29              return parent;
30          }
31          public BinTreeNode left() {
32              return left;
33          }
34          public BinTreeNode right() {
35              return right;
36          }
37          
38          public String   toString() {
39              return "["+obj+"]";
40          }
41      }
42  
43      private abstract class BinTreeIterator implements Iterator {
44          protected BinTreeNodeP p = root;
45          protected BinTreeNodeP q = null;
46          protected int visited = 0;
47  
48          /** Returns true if the iteration has more elements. */
49          public boolean hasNext() {
50              if (visited<size()) {
51                  return true;
52              } else {
53                  return false;
54              }
55          }
56  
57          /** Returns the next element in the iteration. */
58          public abstract Object   next();
59  
60          /** A node of the tree cannot be removed unless it is a leaf */
61          public void remove() throws UnsupportedOperationException   {
62              throw new UnsupportedOperationException  ();
63          }
64      }
65  
66      /** Iterates the nodes of the tree in pre-order (root-left-right) */
67      private class PreIterator extends BinTreeIterator {
68          /** Returns the next element in the iteration. */
69          public Object   next() throws NoSuchElementException {
70              if (p == null || (p == root && q != null)) {
71                  throw new NoSuchElementException();
72              } else {
73                  boolean foundNext = false;
74                  do {
75                      if (q == p.parent) {
76                          q = p;
77                          if (p.left != null) 
78                              p = p.left;
79                          else {
80                              if (p.right != null) 
81                                  p = p.right;
82                              else {
83                                  p = p.parent;
84                              }
85                          }
86                          foundNext = true;
87                      } else if (q == p.left) {
88                          q = p;
89                          if (p.right != null)
90                              p = p.right;
91                          else {
92                              p = p.parent;
93                          }
94                      } else {
95                          q = p;
96                          p = p.parent;
97                      }
98                  } while (p != null && !foundNext);
99                  //System.out.println("p:"+p+" q:"+q);
100                 visited++;
101                 return q;
102             }
103         }
104     }
105 
106     /** Iterates the nodes of the tree in in-order (left-root-right) */
107     private class InIterator extends BinTreeIterator {
108         /** Returns the next element in the iteration. */
109         public Object   next() throws NoSuchElementException {
110             if (p == null) {
111                 throw new NoSuchElementException();
112             } else {
113                 boolean foundNext = false;
114                 do {
115                     if (q == p.parent) {
116                         q = p;
117                         if (p.left != null) 
118                             p = p.left;
119                         else {
120                             if (p.right != null) 
121                                 p = p.right;
122                             else {
123                                 p = p.parent;
124                             }
125                             foundNext = true;
126                         }
127                     } else if (q == p.left) {
128                         q = p;
129                         if (p.right != null)
130                             p = p.right;
131                         else {
132                             p = p.parent;
133                         }
134                         foundNext = true;
135                     } else {
136                         q = p;
137                         p = p.parent;
138                     }
139                 } while (p != null && !foundNext);
140                 visited++;
141                 return q;
142             }
143         }
144     }
145 
146     /** Iterates the nodes of the tree in post-order (left-right-root) */
147     private class PostIterator extends BinTreeIterator {
148         /** Returns the next element in the iteration. */
149         public Object   next() throws NoSuchElementException {
150             if (p == null) {
151                 throw new NoSuchElementException();
152             } else {
153                 boolean foundNext = false;
154                 while (p != null && !foundNext) {
155                     if (q == p.parent) {
156                         q = p;
157                         if (p.left != null) 
158                             p = p.left;
159                         else {
160                             if (p.right != null) 
161                                 p = p.right;
162                             else {
163                                 p = p.parent;
164                                 foundNext = true;
165                             }
166                         }
167                     } else if (q == p.left) {
168                         q = p;
169                         if (p.right != null)
170                             p = p.right;
171                         else {
172                             p = p.parent;
173                             foundNext = true;
174                         }
175                     } else {
176                         q = p;
177                         p = p.parent;
178                         foundNext = true;
179                     }
180                 }
181                 visited++;
182                 return q;
183             }
184         }
185     }
186 
187     /** Returns the root of the tree. */
188     public BinTreeNode root() {
189         return root;
190     }
191     
192     /** Returns the number of nodes in the tree. */
193     public int size() {
194         return getWeight(root);
195     }
196 
197     /** Returns the number of nodes in the subtree of the specified node */ 
198     private int getWeight(BinTreeNodeP node) {
199         if (node != null) {
200             return node.weight;
201         } else {
202             return 0;
203         }
204     }
205 
206     /** Fixes the weights of the given node and of all
207     the nodes all the way to the root of the tree */
208     private void fixWeight(BinTreeNodeP node, int i) {
209         if (i != 0) {
210             while (node != null) {
211                 node.weight += i;
212                 node = node.parent;
213             }
214         }
215     }
216     
217     /** Adds the given object as the root of the tree.
218     If the tree already had a root the link to that node
219     (and possibly many others) is lost.*/
220     public BinTreeNode addRoot(Object   obj) {
221         root = new BinTreeNodeP(obj);
222         return root;
223     }
224 
225     /** Adds the given subTree as the root of the tree. */
226     public void addRootSubTree(BinTree subTree) {
227         subTree.root.parent = null;
228         root = subTree.root;
229     }
230 
231     /** Adds the given object as a left child of the specified parent.
232     If the parent already had a left child the link to that node
233     (and possibly many others) is lost.*/
234     public BinTreeNode addLeftChild(Object   obj, BinTreeNode parentNode) {
235         BinTreeNodeP node = new BinTreeNodeP(obj);
236         BinTreeNodeP p = (BinTreeNodeP)parentNode;
237         fixWeight(p, 1-getWeight(p.left));
238         node.parent = p;
239         p.left = node;
240         return node;
241     }
242 
243     /** Adds the given tree as the left subtree of the specified parent.
244     If the parent already had a left child the link to that node
245     (and possibly many others) is lost.*/
246     public void addLeftSubTree(BinTree subTree, BinTreeNode parentNode) {
247         BinTreeNodeP p = (BinTreeNodeP)parentNode;
248         fixWeight(p, subTree.size()-getWeight(p.left));
249         subTree.root.parent = p;
250         p.left = subTree.root;
251     }
252     
253     /** Adds the given object as a right child of the specified parent.
254     If the parent already had a right child the link to that node
255     (and possibly many others) is lost.*/
256     public BinTreeNode addRightChild(Object   obj, BinTreeNode parentNode) {
257         BinTreeNodeP node = new BinTreeNodeP(obj);
258         BinTreeNodeP p = (BinTreeNodeP)parentNode;
259         fixWeight(p, 1-getWeight(p.right));
260         node.parent = p;
261         p.right = node;
262         return node;
263     }
264     
265     /** Adds the given tree as the right subtree of the specified parent.
266     If the parent already had a right child the link to that node
267     (and possibly many others) is lost.*/
268     public void addRightSubTree(BinTree subTree, BinTreeNode parentNode) {
269         BinTreeNodeP p = (BinTreeNodeP)parentNode;
270         fixWeight(p, subTree.size()-getWeight(p.right));
271         subTree.root.parent = p;
272         p.right = subTree.root;
273     }
274     
275     /** Removes the specified node and all its children from the tree. */
276     public void removeNode(BinTreeNode node) {
277         BinTreeNodeP p = (BinTreeNodeP)node;
278         if (p == root) {
279             root = null;
280         } else {
281             fixWeight(p.parent, -getWeight(p));
282             if (p.parent.left == p) {
283                 p.parent.left = null;
284             } else {
285                 p.parent.right = null;
286             }
287             p.parent = null;
288         }
289     }
290 
291     /** Returns an Iteratator that over the nodes of this
292     tree in pre-order sequence (root-left-right). */
293     public Iterator preIterator() {
294         return new PreIterator();
295     }
296 
297     /** Returns an Iteratator that over the nodes of this
298     tree in in-order sequence (left-root-right). */
299     public Iterator inIterator() {
300         return new InIterator();
301     }
302 
303     /** Returns an Iteratator that over the nodes of this
304     tree in post-order sequence (left-right-root) */
305     public Iterator postIterator() {
306         return new PostIterator();
307     }
308     
309     /** Returns true if the tree has no nodes. */
310     public boolean IsEmpty() {
311         return root == null;
312     }
313 }
314
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags