85 *
86 * @author Rob Davis
87 */
88 @SuppressWarnings("serial") // Same-version serialization only
89 public class DefaultMutableTreeNode implements Cloneable,
90 MutableTreeNode, Serializable
91 {
92 private static final long serialVersionUID = -4298474751201349152L;
93
94 /**
95 * An enumeration that is always empty. This is used when an enumeration
96 * of a leaf node's children is requested.
97 */
98 static public final Enumeration<TreeNode> EMPTY_ENUMERATION
99 = Collections.emptyEnumeration();
100
101 /** this node's parent, or null if this node has no parent */
102 protected MutableTreeNode parent;
103
104 /** array of children, may be null if this node has no children */
105 protected Vector children;
106
107 /** optional user object */
108 transient protected Object userObject;
109
110 /** true if the node is able to have children */
111 protected boolean allowsChildren;
112
113
114 /**
115 * Creates a tree node that has no parent and no children, but which
116 * allows children.
117 */
118 public DefaultMutableTreeNode() {
119 this(null);
120 }
121
122 /**
123 * Creates a tree node with no parent, no children, but which allows
124 * children, and initializes it with the specified user object.
125 *
170 * @exception IllegalStateException if this node does not allow
171 * children
172 * @see #isNodeDescendant
173 */
174 public void insert(MutableTreeNode newChild, int childIndex) {
175 if (!allowsChildren) {
176 throw new IllegalStateException("node does not allow children");
177 } else if (newChild == null) {
178 throw new IllegalArgumentException("new child is null");
179 } else if (isNodeAncestor(newChild)) {
180 throw new IllegalArgumentException("new child is an ancestor");
181 }
182
183 MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent();
184
185 if (oldParent != null) {
186 oldParent.remove(newChild);
187 }
188 newChild.setParent(this);
189 if (children == null) {
190 children = new Vector();
191 }
192 children.insertElementAt(newChild, childIndex);
193 }
194
195 /**
196 * Removes the child at the specified index from this node's children
197 * and sets that node's parent to null. The child node to remove
198 * must be a <code>MutableTreeNode</code>.
199 *
200 * @param childIndex the index in this node's child array
201 * of the child to remove
202 * @exception ArrayIndexOutOfBoundsException if
203 * <code>childIndex</code> is out of bounds
204 */
205 public void remove(int childIndex) {
206 MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex);
207 children.removeElementAt(childIndex);
208 child.setParent(null);
209 }
210
226 * Returns this node's parent or null if this node has no parent.
227 *
228 * @return this node's parent TreeNode, or null if this node has no parent
229 */
230 public TreeNode getParent() {
231 return parent;
232 }
233
234 /**
235 * Returns the child at the specified index in this node's child array.
236 *
237 * @param index an index into this node's child array
238 * @exception ArrayIndexOutOfBoundsException if <code>index</code>
239 * is out of bounds
240 * @return the TreeNode in this node's child array at the specified index
241 */
242 public TreeNode getChildAt(int index) {
243 if (children == null) {
244 throw new ArrayIndexOutOfBoundsException("node has no children");
245 }
246 return (TreeNode)children.elementAt(index);
247 }
248
249 /**
250 * Returns the number of children of this node.
251 *
252 * @return an int giving the number of children of this node
253 */
254 public int getChildCount() {
255 if (children == null) {
256 return 0;
257 } else {
258 return children.size();
259 }
260 }
261
262 /**
263 * Returns the index of the specified child in this node's child array.
264 * If the specified node is not a child of this node, returns
265 * <code>-1</code>. This method performs a linear search and is O(n)
266 * where n is the number of children.
273 * a child of this node
274 */
275 public int getIndex(TreeNode aChild) {
276 if (aChild == null) {
277 throw new IllegalArgumentException("argument is null");
278 }
279
280 if (!isNodeChild(aChild)) {
281 return -1;
282 }
283 return children.indexOf(aChild); // linear search
284 }
285
286 /**
287 * Creates and returns a forward-order enumeration of this node's
288 * children. Modifying this node's child array invalidates any child
289 * enumerations created before the modification.
290 *
291 * @return an Enumeration of this node's children
292 */
293 public Enumeration children() {
294 if (children == null) {
295 return EMPTY_ENUMERATION;
296 } else {
297 return children.elements();
298 }
299 }
300
301 /**
302 * Determines whether or not this node is allowed to have children.
303 * If <code>allows</code> is false, all of this node's children are
304 * removed.
305 * <p>
306 * Note: By default, a node allows children.
307 *
308 * @param allows true if this node is allowed to have children
309 */
310 public void setAllowsChildren(boolean allows) {
311 if (allows != allowsChildren) {
312 allowsChildren = allows;
313 if (!allowsChildren) {
540 * @return true if <code>aNode</code> is in the same tree as this node;
541 * false if <code>aNode</code> is null
542 */
543 public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
544 return (aNode != null) && (getRoot() == aNode.getRoot());
545 }
546
547
548 /**
549 * Returns the depth of the tree rooted at this node -- the longest
550 * distance from this node to a leaf. If this node has no children,
551 * returns 0. This operation is much more expensive than
552 * <code>getLevel()</code> because it must effectively traverse the entire
553 * tree rooted at this node.
554 *
555 * @see #getLevel
556 * @return the depth of the tree whose root is this node
557 */
558 public int getDepth() {
559 Object last = null;
560 Enumeration enum_ = breadthFirstEnumeration();
561
562 while (enum_.hasMoreElements()) {
563 last = enum_.nextElement();
564 }
565
566 if (last == null) {
567 throw new Error ("nodes should be null");
568 }
569
570 return ((DefaultMutableTreeNode)last).getLevel() - getLevel();
571 }
572
573
574
575 /**
576 * Returns the number of levels above this node -- the distance from
577 * the root to this node. If this node is the root, returns 0.
578 *
579 * @see #getDepth
580 * @return the number of levels above this node
748 if (previousSibling.getChildCount() == 0)
749 return previousSibling;
750 else
751 return previousSibling.getLastLeaf();
752 } else {
753 return myParent;
754 }
755 }
756
757 /**
758 * Creates and returns an enumeration that traverses the subtree rooted at
759 * this node in preorder. The first node returned by the enumeration's
760 * <code>nextElement()</code> method is this node.<P>
761 *
762 * Modifying the tree by inserting, removing, or moving a node invalidates
763 * any enumerations created before the modification.
764 *
765 * @see #postorderEnumeration
766 * @return an enumeration for traversing the tree in preorder
767 */
768 public Enumeration preorderEnumeration() {
769 return new PreorderEnumeration(this);
770 }
771
772 /**
773 * Creates and returns an enumeration that traverses the subtree rooted at
774 * this node in postorder. The first node returned by the enumeration's
775 * <code>nextElement()</code> method is the leftmost leaf. This is the
776 * same as a depth-first traversal.<P>
777 *
778 * Modifying the tree by inserting, removing, or moving a node invalidates
779 * any enumerations created before the modification.
780 *
781 * @see #depthFirstEnumeration
782 * @see #preorderEnumeration
783 * @return an enumeration for traversing the tree in postorder
784 */
785 public Enumeration postorderEnumeration() {
786 return new PostorderEnumeration(this);
787 }
788
789 /**
790 * Creates and returns an enumeration that traverses the subtree rooted at
791 * this node in breadth-first order. The first node returned by the
792 * enumeration's <code>nextElement()</code> method is this node.<P>
793 *
794 * Modifying the tree by inserting, removing, or moving a node invalidates
795 * any enumerations created before the modification.
796 *
797 * @see #depthFirstEnumeration
798 * @return an enumeration for traversing the tree in breadth-first order
799 */
800 public Enumeration breadthFirstEnumeration() {
801 return new BreadthFirstEnumeration(this);
802 }
803
804 /**
805 * Creates and returns an enumeration that traverses the subtree rooted at
806 * this node in depth-first order. The first node returned by the
807 * enumeration's <code>nextElement()</code> method is the leftmost leaf.
808 * This is the same as a postorder traversal.<P>
809 *
810 * Modifying the tree by inserting, removing, or moving a node invalidates
811 * any enumerations created before the modification.
812 *
813 * @see #breadthFirstEnumeration
814 * @see #postorderEnumeration
815 * @return an enumeration for traversing the tree in depth-first order
816 */
817 public Enumeration depthFirstEnumeration() {
818 return postorderEnumeration();
819 }
820
821 /**
822 * Creates and returns an enumeration that follows the path from
823 * <code>ancestor</code> to this node. The enumeration's
824 * <code>nextElement()</code> method first returns <code>ancestor</code>,
825 * then the child of <code>ancestor</code> that is an ancestor of this
826 * node, and so on, and finally returns this node. Creation of the
827 * enumeration is O(m) where m is the number of nodes between this node
828 * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code>
829 * message is O(1).<P>
830 *
831 * Modifying the tree by inserting, removing, or moving a node invalidates
832 * any enumerations created before the modification.
833 *
834 * @param ancestor the node to start enumeration from
835 * @see #isNodeAncestor
836 * @see #isNodeDescendant
837 * @exception IllegalArgumentException if <code>ancestor</code> is
838 * not an ancestor of this node
839 * @return an enumeration for following the path from an ancestor of
840 * this node to this one
841 */
842 public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
843 return new PathBetweenNodesEnumeration(ancestor, this);
844 }
845
846
847 //
848 // Child Queries
849 //
850
851 /**
852 * Returns true if <code>aNode</code> is a child of this node. If
853 * <code>aNode</code> is null, this method returns false.
854 *
855 * @param aNode the node to determinate whether it is a child
856 * @return true if <code>aNode</code> is a child of this node; false if
857 * <code>aNode</code> is null
858 */
859 public boolean isNodeChild(TreeNode aNode) {
860 boolean retval;
861
862 if (aNode == null) {
1201
1202 if (previousSibling != null)
1203 return previousSibling.getLastLeaf();
1204
1205 return myParent.getPreviousLeaf(); // tail recursion
1206 }
1207
1208
1209 /**
1210 * Returns the total number of leaves that are descendants of this node.
1211 * If this node is a leaf, returns <code>1</code>. This method is O(n)
1212 * where n is the number of descendants of this node.
1213 *
1214 * @see #isNodeAncestor
1215 * @return the number of leaves beneath this node
1216 */
1217 public int getLeafCount() {
1218 int count = 0;
1219
1220 TreeNode node;
1221 Enumeration enum_ = breadthFirstEnumeration(); // order matters not
1222
1223 while (enum_.hasMoreElements()) {
1224 node = (TreeNode)enum_.nextElement();
1225 if (node.isLeaf()) {
1226 count++;
1227 }
1228 }
1229
1230 if (count < 1) {
1231 throw new Error("tree has zero leaves");
1232 }
1233
1234 return count;
1235 }
1236
1237
1238 //
1239 // Overrides
1240 //
1241
1242 /**
1243 * Returns the result of sending <code>toString()</code> to this node's
1244 * user object, or the empty string if the node has no user object.
1291 tValues[1] = userObject;
1292 }
1293 else
1294 tValues = new Object[0];
1295 s.writeObject(tValues);
1296 }
1297
1298 private void readObject(ObjectInputStream s)
1299 throws IOException, ClassNotFoundException {
1300 Object[] tValues;
1301
1302 s.defaultReadObject();
1303
1304 tValues = (Object[])s.readObject();
1305
1306 if(tValues.length > 0 && tValues[0].equals("userObject"))
1307 userObject = tValues[1];
1308 }
1309
1310 private final class PreorderEnumeration implements Enumeration<TreeNode> {
1311 private final Stack<Enumeration> stack = new Stack<Enumeration>();
1312
1313 public PreorderEnumeration(TreeNode rootNode) {
1314 super();
1315 Vector<TreeNode> v = new Vector<TreeNode>(1);
1316 v.addElement(rootNode); // PENDING: don't really need a vector
1317 stack.push(v.elements());
1318 }
1319
1320 public boolean hasMoreElements() {
1321 return (!stack.empty() && stack.peek().hasMoreElements());
1322 }
1323
1324 public TreeNode nextElement() {
1325 Enumeration enumer = stack.peek();
1326 TreeNode node = (TreeNode)enumer.nextElement();
1327 Enumeration children = node.children();
1328
1329 if (!enumer.hasMoreElements()) {
1330 stack.pop();
1331 }
1332 if (children.hasMoreElements()) {
1333 stack.push(children);
1334 }
1335 return node;
1336 }
1337
1338 } // End of class PreorderEnumeration
1339
1340
1341
1342 final class PostorderEnumeration implements Enumeration<TreeNode> {
1343 protected TreeNode root;
1344 protected Enumeration<TreeNode> children;
1345 protected Enumeration<TreeNode> subtree;
1346
1347 public PostorderEnumeration(TreeNode rootNode) {
1375
1376
1377
1378 final class BreadthFirstEnumeration implements Enumeration<TreeNode> {
1379 protected Queue queue;
1380
1381 public BreadthFirstEnumeration(TreeNode rootNode) {
1382 super();
1383 Vector<TreeNode> v = new Vector<TreeNode>(1);
1384 v.addElement(rootNode); // PENDING: don't really need a vector
1385 queue = new Queue();
1386 queue.enqueue(v.elements());
1387 }
1388
1389 public boolean hasMoreElements() {
1390 return (!queue.isEmpty() &&
1391 ((Enumeration)queue.firstObject()).hasMoreElements());
1392 }
1393
1394 public TreeNode nextElement() {
1395 Enumeration enumer = (Enumeration)queue.firstObject();
1396 TreeNode node = (TreeNode)enumer.nextElement();
1397 Enumeration children = node.children();
1398
1399 if (!enumer.hasMoreElements()) {
1400 queue.dequeue();
1401 }
1402 if (children.hasMoreElements()) {
1403 queue.enqueue(children);
1404 }
1405 return node;
1406 }
1407
1408
1409 // A simple queue with a linked list data structure.
1410 final class Queue {
1411 QNode head; // null if empty
1412 QNode tail;
1413
1414 final class QNode {
1415 public Object object;
1416 public QNode next; // null if end
1417 public QNode(Object object, QNode next) {
|
85 *
86 * @author Rob Davis
87 */
88 @SuppressWarnings("serial") // Same-version serialization only
89 public class DefaultMutableTreeNode implements Cloneable,
90 MutableTreeNode, Serializable
91 {
92 private static final long serialVersionUID = -4298474751201349152L;
93
94 /**
95 * An enumeration that is always empty. This is used when an enumeration
96 * of a leaf node's children is requested.
97 */
98 static public final Enumeration<TreeNode> EMPTY_ENUMERATION
99 = Collections.emptyEnumeration();
100
101 /** this node's parent, or null if this node has no parent */
102 protected MutableTreeNode parent;
103
104 /** array of children, may be null if this node has no children */
105 protected Vector<TreeNode> children;
106
107 /** optional user object */
108 transient protected Object userObject;
109
110 /** true if the node is able to have children */
111 protected boolean allowsChildren;
112
113
114 /**
115 * Creates a tree node that has no parent and no children, but which
116 * allows children.
117 */
118 public DefaultMutableTreeNode() {
119 this(null);
120 }
121
122 /**
123 * Creates a tree node with no parent, no children, but which allows
124 * children, and initializes it with the specified user object.
125 *
170 * @exception IllegalStateException if this node does not allow
171 * children
172 * @see #isNodeDescendant
173 */
174 public void insert(MutableTreeNode newChild, int childIndex) {
175 if (!allowsChildren) {
176 throw new IllegalStateException("node does not allow children");
177 } else if (newChild == null) {
178 throw new IllegalArgumentException("new child is null");
179 } else if (isNodeAncestor(newChild)) {
180 throw new IllegalArgumentException("new child is an ancestor");
181 }
182
183 MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent();
184
185 if (oldParent != null) {
186 oldParent.remove(newChild);
187 }
188 newChild.setParent(this);
189 if (children == null) {
190 children = new Vector<>();
191 }
192 children.insertElementAt(newChild, childIndex);
193 }
194
195 /**
196 * Removes the child at the specified index from this node's children
197 * and sets that node's parent to null. The child node to remove
198 * must be a <code>MutableTreeNode</code>.
199 *
200 * @param childIndex the index in this node's child array
201 * of the child to remove
202 * @exception ArrayIndexOutOfBoundsException if
203 * <code>childIndex</code> is out of bounds
204 */
205 public void remove(int childIndex) {
206 MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex);
207 children.removeElementAt(childIndex);
208 child.setParent(null);
209 }
210
226 * Returns this node's parent or null if this node has no parent.
227 *
228 * @return this node's parent TreeNode, or null if this node has no parent
229 */
230 public TreeNode getParent() {
231 return parent;
232 }
233
234 /**
235 * Returns the child at the specified index in this node's child array.
236 *
237 * @param index an index into this node's child array
238 * @exception ArrayIndexOutOfBoundsException if <code>index</code>
239 * is out of bounds
240 * @return the TreeNode in this node's child array at the specified index
241 */
242 public TreeNode getChildAt(int index) {
243 if (children == null) {
244 throw new ArrayIndexOutOfBoundsException("node has no children");
245 }
246 return children.elementAt(index);
247 }
248
249 /**
250 * Returns the number of children of this node.
251 *
252 * @return an int giving the number of children of this node
253 */
254 public int getChildCount() {
255 if (children == null) {
256 return 0;
257 } else {
258 return children.size();
259 }
260 }
261
262 /**
263 * Returns the index of the specified child in this node's child array.
264 * If the specified node is not a child of this node, returns
265 * <code>-1</code>. This method performs a linear search and is O(n)
266 * where n is the number of children.
273 * a child of this node
274 */
275 public int getIndex(TreeNode aChild) {
276 if (aChild == null) {
277 throw new IllegalArgumentException("argument is null");
278 }
279
280 if (!isNodeChild(aChild)) {
281 return -1;
282 }
283 return children.indexOf(aChild); // linear search
284 }
285
286 /**
287 * Creates and returns a forward-order enumeration of this node's
288 * children. Modifying this node's child array invalidates any child
289 * enumerations created before the modification.
290 *
291 * @return an Enumeration of this node's children
292 */
293 public Enumeration<TreeNode> children() {
294 if (children == null) {
295 return EMPTY_ENUMERATION;
296 } else {
297 return children.elements();
298 }
299 }
300
301 /**
302 * Determines whether or not this node is allowed to have children.
303 * If <code>allows</code> is false, all of this node's children are
304 * removed.
305 * <p>
306 * Note: By default, a node allows children.
307 *
308 * @param allows true if this node is allowed to have children
309 */
310 public void setAllowsChildren(boolean allows) {
311 if (allows != allowsChildren) {
312 allowsChildren = allows;
313 if (!allowsChildren) {
540 * @return true if <code>aNode</code> is in the same tree as this node;
541 * false if <code>aNode</code> is null
542 */
543 public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
544 return (aNode != null) && (getRoot() == aNode.getRoot());
545 }
546
547
548 /**
549 * Returns the depth of the tree rooted at this node -- the longest
550 * distance from this node to a leaf. If this node has no children,
551 * returns 0. This operation is much more expensive than
552 * <code>getLevel()</code> because it must effectively traverse the entire
553 * tree rooted at this node.
554 *
555 * @see #getLevel
556 * @return the depth of the tree whose root is this node
557 */
558 public int getDepth() {
559 Object last = null;
560 Enumeration<TreeNode> enum_ = breadthFirstEnumeration();
561
562 while (enum_.hasMoreElements()) {
563 last = enum_.nextElement();
564 }
565
566 if (last == null) {
567 throw new Error ("nodes should be null");
568 }
569
570 return ((DefaultMutableTreeNode)last).getLevel() - getLevel();
571 }
572
573
574
575 /**
576 * Returns the number of levels above this node -- the distance from
577 * the root to this node. If this node is the root, returns 0.
578 *
579 * @see #getDepth
580 * @return the number of levels above this node
748 if (previousSibling.getChildCount() == 0)
749 return previousSibling;
750 else
751 return previousSibling.getLastLeaf();
752 } else {
753 return myParent;
754 }
755 }
756
757 /**
758 * Creates and returns an enumeration that traverses the subtree rooted at
759 * this node in preorder. The first node returned by the enumeration's
760 * <code>nextElement()</code> method is this node.<P>
761 *
762 * Modifying the tree by inserting, removing, or moving a node invalidates
763 * any enumerations created before the modification.
764 *
765 * @see #postorderEnumeration
766 * @return an enumeration for traversing the tree in preorder
767 */
768 public Enumeration<TreeNode> preorderEnumeration() {
769 return new PreorderEnumeration(this);
770 }
771
772 /**
773 * Creates and returns an enumeration that traverses the subtree rooted at
774 * this node in postorder. The first node returned by the enumeration's
775 * <code>nextElement()</code> method is the leftmost leaf. This is the
776 * same as a depth-first traversal.<P>
777 *
778 * Modifying the tree by inserting, removing, or moving a node invalidates
779 * any enumerations created before the modification.
780 *
781 * @see #depthFirstEnumeration
782 * @see #preorderEnumeration
783 * @return an enumeration for traversing the tree in postorder
784 */
785 public Enumeration<TreeNode> postorderEnumeration() {
786 return new PostorderEnumeration(this);
787 }
788
789 /**
790 * Creates and returns an enumeration that traverses the subtree rooted at
791 * this node in breadth-first order. The first node returned by the
792 * enumeration's <code>nextElement()</code> method is this node.<P>
793 *
794 * Modifying the tree by inserting, removing, or moving a node invalidates
795 * any enumerations created before the modification.
796 *
797 * @see #depthFirstEnumeration
798 * @return an enumeration for traversing the tree in breadth-first order
799 */
800 public Enumeration<TreeNode> breadthFirstEnumeration() {
801 return new BreadthFirstEnumeration(this);
802 }
803
804 /**
805 * Creates and returns an enumeration that traverses the subtree rooted at
806 * this node in depth-first order. The first node returned by the
807 * enumeration's <code>nextElement()</code> method is the leftmost leaf.
808 * This is the same as a postorder traversal.<P>
809 *
810 * Modifying the tree by inserting, removing, or moving a node invalidates
811 * any enumerations created before the modification.
812 *
813 * @see #breadthFirstEnumeration
814 * @see #postorderEnumeration
815 * @return an enumeration for traversing the tree in depth-first order
816 */
817 public Enumeration<TreeNode> depthFirstEnumeration() {
818 return postorderEnumeration();
819 }
820
821 /**
822 * Creates and returns an enumeration that follows the path from
823 * <code>ancestor</code> to this node. The enumeration's
824 * <code>nextElement()</code> method first returns <code>ancestor</code>,
825 * then the child of <code>ancestor</code> that is an ancestor of this
826 * node, and so on, and finally returns this node. Creation of the
827 * enumeration is O(m) where m is the number of nodes between this node
828 * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code>
829 * message is O(1).<P>
830 *
831 * Modifying the tree by inserting, removing, or moving a node invalidates
832 * any enumerations created before the modification.
833 *
834 * @param ancestor the node to start enumeration from
835 * @see #isNodeAncestor
836 * @see #isNodeDescendant
837 * @exception IllegalArgumentException if <code>ancestor</code> is
838 * not an ancestor of this node
839 * @return an enumeration for following the path from an ancestor of
840 * this node to this one
841 */
842 public Enumeration<TreeNode> pathFromAncestorEnumeration(TreeNode ancestor) {
843 return new PathBetweenNodesEnumeration(ancestor, this);
844 }
845
846
847 //
848 // Child Queries
849 //
850
851 /**
852 * Returns true if <code>aNode</code> is a child of this node. If
853 * <code>aNode</code> is null, this method returns false.
854 *
855 * @param aNode the node to determinate whether it is a child
856 * @return true if <code>aNode</code> is a child of this node; false if
857 * <code>aNode</code> is null
858 */
859 public boolean isNodeChild(TreeNode aNode) {
860 boolean retval;
861
862 if (aNode == null) {
1201
1202 if (previousSibling != null)
1203 return previousSibling.getLastLeaf();
1204
1205 return myParent.getPreviousLeaf(); // tail recursion
1206 }
1207
1208
1209 /**
1210 * Returns the total number of leaves that are descendants of this node.
1211 * If this node is a leaf, returns <code>1</code>. This method is O(n)
1212 * where n is the number of descendants of this node.
1213 *
1214 * @see #isNodeAncestor
1215 * @return the number of leaves beneath this node
1216 */
1217 public int getLeafCount() {
1218 int count = 0;
1219
1220 TreeNode node;
1221 Enumeration<TreeNode> enum_ = breadthFirstEnumeration(); // order matters not
1222
1223 while (enum_.hasMoreElements()) {
1224 node = enum_.nextElement();
1225 if (node.isLeaf()) {
1226 count++;
1227 }
1228 }
1229
1230 if (count < 1) {
1231 throw new Error("tree has zero leaves");
1232 }
1233
1234 return count;
1235 }
1236
1237
1238 //
1239 // Overrides
1240 //
1241
1242 /**
1243 * Returns the result of sending <code>toString()</code> to this node's
1244 * user object, or the empty string if the node has no user object.
1291 tValues[1] = userObject;
1292 }
1293 else
1294 tValues = new Object[0];
1295 s.writeObject(tValues);
1296 }
1297
1298 private void readObject(ObjectInputStream s)
1299 throws IOException, ClassNotFoundException {
1300 Object[] tValues;
1301
1302 s.defaultReadObject();
1303
1304 tValues = (Object[])s.readObject();
1305
1306 if(tValues.length > 0 && tValues[0].equals("userObject"))
1307 userObject = tValues[1];
1308 }
1309
1310 private final class PreorderEnumeration implements Enumeration<TreeNode> {
1311 private final Stack<Enumeration<TreeNode>> stack = new Stack<>();
1312
1313 public PreorderEnumeration(TreeNode rootNode) {
1314 super();
1315 Vector<TreeNode> v = new Vector<TreeNode>(1);
1316 v.addElement(rootNode); // PENDING: don't really need a vector
1317 stack.push(v.elements());
1318 }
1319
1320 public boolean hasMoreElements() {
1321 return (!stack.empty() && stack.peek().hasMoreElements());
1322 }
1323
1324 public TreeNode nextElement() {
1325 Enumeration<TreeNode> enumer = stack.peek();
1326 TreeNode node = enumer.nextElement();
1327 @SuppressWarnings("unchecked")
1328 Enumeration<TreeNode> children = node.children();
1329
1330 if (!enumer.hasMoreElements()) {
1331 stack.pop();
1332 }
1333 if (children.hasMoreElements()) {
1334 stack.push(children);
1335 }
1336 return node;
1337 }
1338
1339 } // End of class PreorderEnumeration
1340
1341
1342
1343 final class PostorderEnumeration implements Enumeration<TreeNode> {
1344 protected TreeNode root;
1345 protected Enumeration<TreeNode> children;
1346 protected Enumeration<TreeNode> subtree;
1347
1348 public PostorderEnumeration(TreeNode rootNode) {
1376
1377
1378
1379 final class BreadthFirstEnumeration implements Enumeration<TreeNode> {
1380 protected Queue queue;
1381
1382 public BreadthFirstEnumeration(TreeNode rootNode) {
1383 super();
1384 Vector<TreeNode> v = new Vector<TreeNode>(1);
1385 v.addElement(rootNode); // PENDING: don't really need a vector
1386 queue = new Queue();
1387 queue.enqueue(v.elements());
1388 }
1389
1390 public boolean hasMoreElements() {
1391 return (!queue.isEmpty() &&
1392 ((Enumeration)queue.firstObject()).hasMoreElements());
1393 }
1394
1395 public TreeNode nextElement() {
1396 Enumeration<?> enumer = (Enumeration)queue.firstObject();
1397 TreeNode node = (TreeNode)enumer.nextElement();
1398 Enumeration<?> children = node.children();
1399
1400 if (!enumer.hasMoreElements()) {
1401 queue.dequeue();
1402 }
1403 if (children.hasMoreElements()) {
1404 queue.enqueue(children);
1405 }
1406 return node;
1407 }
1408
1409
1410 // A simple queue with a linked list data structure.
1411 final class Queue {
1412 QNode head; // null if empty
1413 QNode tail;
1414
1415 final class QNode {
1416 public Object object;
1417 public QNode next; // null if end
1418 public QNode(Object object, QNode next) {
|