为简化实际业务场景中常见的菜单、组织架构等树型数据结构的处理,避免代码中出现相似代码和复杂代码,采用迭代器模式,设计一套树迭代器,支持业务场景中常用的前序遍历、后序遍历和层级遍历。
2、UML图 3、使用demo1、SimpleTree
@Data
public class SimpleTree {
private String nodeName;
private List children;
}
2、IteratorClient
public class IteratorClient {
public static void main(String[] args) {
Tree tree = new Tree<>(initTree(), SimpleTree::getChildren, SimpleTree::setChildren);
TreeIterator iterator = tree.iterator(Tree.TreeIteratorEnum.LEVEL);
while (iterator.hasNext()) {
SimpleTree item = iterator.next();
System.out.println(item.getNodeName());
// 删除当前节点
// iterator.remove();
// 获取当前节点的父节点
// SimpleTree currentParentNode = iterator.getCurrentParentNode();
// 获取当前节点的子节点
// List children = item.getChildren();
}
}
private static List initTree() {
List result = new ArrayList<>();
// ... 填充树节点
return result;
}
}
4、树迭代器源码
1、TreeIterator
public abstract class TreeIteratorimplements Iterator { T currentNode; T currentParentNode; Function > getChildrenFun; TreeIterator(Function > getChildrenFun) { this.getChildrenFun = getChildrenFun; } public T getCurrentParentNode() { return currentParentNode; } @Override public void remove() { // 判断当前父节点是否已取出 if (this.currentParentNode != null) { // 获取子节点集合 List nodeList = getChildrenFun.apply(this.currentParentNode); // 移除当前子节点 if (CollectionUtil.isNotEmpty(nodeList)) { nodeList.remove(this.currentNode); } } } }
2、TreeLevelIterator
public class TreeLevelIteratorextends TreeIterator { private Deque queue = new LinkedList<>(); private Deque parentQueue = new LinkedList<>(); public TreeLevelIterator(Function > getChildrenFun, T root) { super(getChildrenFun); pushQueue(root); } private void pushQueue(T root) { if (root == null) { return; } List nodeList = this.getChildrenFun.apply(root); if (CollectionUtil.isEmpty(nodeList)) { return; } nodeList.forEach(item -> { this.queue.add(item); this.parentQueue.add(root); }); } @Override public boolean hasNext() { return !this.queue.isEmpty() && !this.parentQueue.isEmpty(); } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } // pop双队列中第一个节点 this.currentNode = this.queue.pop(); this.currentParentNode = this.parentQueue.pop(); // 子节点入队列 pushQueue(this.currentNode); return this.currentNode; } }
3、TreePostIterator
public class TreePostIteratorextends TreeIterator { private Deque queue = new LinkedList<>(); private Deque parentQueue = new LinkedList<>(); public TreePostIterator(Function > getChildrenFun, T root) { super(getChildrenFun); initQueue(root); } @Override public boolean hasNext() { return !this.queue.isEmpty() && !this.parentQueue.isEmpty(); } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } // pop双队列中的第一个节点 this.currentNode = this.queue.pop(); this.currentParentNode = this.parentQueue.pop(); return this.currentNode; } private void initQueue(T root) { if (root == null) { return; } List nodeList = this.getChildrenFun.apply(root); if (CollectionUtil.isEmpty(nodeList)) { return; } // 创建临时栈,将二级节点入栈 Stack stack = new Stack<>(); Stack parentStack = new Stack<>(); nodeList.forEach(item -> { stack.push(item); parentStack.push(root); }); // 遍历树 while (!stack.isEmpty()) { // pop子节点和对应的父节点 T node = stack.pop(); T parentNode = parentStack.pop(); // 子节点和父节点入队列 this.queue.push(node); this.parentQueue.push(parentNode); List subNodeList = this.getChildrenFun.apply(node); if (CollectionUtil.isNotEmpty(subNodeList)) { subNodeList.forEach(item -> { stack.push(item); parentStack.push(node); }); } } } }
4、TreePreIterator
public class TreePreIteratorextends TreeIterator { private Stack stack = new Stack<>(); private Stack parentStack = new Stack<>(); public TreePreIterator(Function > getChildrenFun, T root) { super(getChildrenFun); pushChildrenToStack(root); } @Override public boolean hasNext() { return !this.stack.isEmpty() && !this.parentStack.isEmpty(); } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } // pop双栈中最后一个节点 this.currentNode = this.stack.pop(); this.currentParentNode = this.parentStack.pop(); // 子节点入栈 pushChildrenToStack(this.currentNode); return this.currentNode; } private void pushChildrenToStack(T node) { if (node == null) { return; } // 查询子节点 List nodeList = this.getChildrenFun.apply(node); if (CollectionUtil.isEmpty(nodeList)) { return; } // 先压右子节点,再压左子节点 for (int i = nodeList.size() - 1; i >= 0; i--) { // 子节点入栈 this.stack.push(nodeList.get(i)); // 子节点对应的父节点入栈 this.parentStack.push(node); } } }
5、Tree
public class Tree{ private T root; private Function > getChildrenFun; @SuppressWarnings("unchecked") public Tree(List rootList, Function > getChildrenFun, BiConsumer > setChildrenFun) { try { this.getChildrenFun = getChildrenFun; if (CollectionUtil.isNotEmpty(rootList)) { T firstRoot = rootList.get(0); T newRoot = (T) firstRoot.getClass().newInstance(); setChildrenFun.accept(newRoot, rootList); this.root = newRoot; } else { this.root = null; } } catch (Exception e) { e.printStackTrace(); throw new ClassCastException(); } } public TreeIterator iterator(TreeIteratorEnum treeIteratorEnum) { TreeIterator iterator; switch (treeIteratorEnum) { case PRE: iterator = new TreePreIterator<>(this.getChildrenFun, this.root); break; case LEVEL: iterator = new TreeLevelIterator<>(this.getChildrenFun, this.root); break; case POST: iterator = new TreePostIterator<>(this.getChildrenFun, this.root); break; default: iterator = new TreePreIterator<>(this.getChildrenFun, this.root); break; } return iterator; } public enum TreeIteratorEnum { PRE, POST, LEVEL } }



