0001 /** 0002 * 基于列表实现的树迭代器 0003 */ 0004 0005 package dsa; 0006 0007 public class IteratorTree implements Iterator { 0008 private List list;//列表 0009 private Position nextPosition;//当前(下一个)元素的位置 0010 0011 //默认构造方法 0012 public IteratorTree() { list = null; } 0013 0014 //前序遍历 0015 public void elementsPreorderIterator(TreeLinkedList T) { 0016 if (null == T) return;//递归基 0017 list.insertLast(T);//首先输出当前节点 0018 TreeLinkedList subtree = T.getFirstChild();//从当前节点的长子开始 0019 while (null != subtree) {//依次对当前节点的各个孩子 0020 this.elementsPreorderIterator(subtree);//做前序遍历 0021 subtree = subtree.getNextSibling(); 0022 } 0023 } 0024 0025 //后序遍历 0026 public void elementsPostorderIterator(TreeLinkedList T) { 0027 if (null == T) return;//递归基 0028 TreeLinkedList subtree = T.getFirstChild();//从当前节点的长子开始 0029 while (null != subtree) {//依次对当前节点的各个孩子 0030 this.elementsPostorderIterator(subtree);//做后序遍历 0031 subtree = subtree.getNextSibling(); 0032 } 0033 list.insertLast(T);//当所有后代都访问过后,最后才访问当前节点 0034 } 0035 0036 //层次遍历 0037 public void levelTraversalIterator(TreeLinkedList T) { 0038 if (null == T) return; 0039 Queue_List Q = new Queue_List();//空队 0040 Q.enqueue(T);//根节点入队 0041 while (!Q.isEmpty()) {//在队列重新变空之前 0042 TreeLinkedList tree = (TreeLinkedList) (Q.dequeue());//取出队列首节点 0043 list.insertLast(tree);//将新出队的节点接入迭代器中 0044 TreeLinkedList subtree = tree.getFirstChild();//从tree的第一个孩子起 0045 while (null != subtree) {//依次找出所有孩子,并 0046 Q.enqueue(subtree);//将其加至队列中 0047 subtree = subtree.getNextSibling(); 0048 } 0049 } 0050 } 0051 0052 //检查迭代器中是否还有剩余的元素 0053 public boolean hasNext() { return (null != nextPosition); } 0054 0055 //返回迭代器中的下一元素 0056 public Object getNext() throws ExceptionNoSuchElement { 0057 if (!hasNext()) throw new ExceptionNoSuchElement("No next position"); 0058 Position currentPosition = nextPosition; 0059 if (currentPosition == list.last())//若已到达尾元素,则 0060 nextPosition = null;//不再有下一元素 0061 else//否则 0062 nextPosition = list.getNext(currentPosition);//转向下一元素 0063 return currentPosition.getElem(); 0064 } 0065 }