栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java树迭代器(支持前序、后序和层级遍历)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java树迭代器(支持前序、后序和层级遍历)

1、设计背景

为简化实际业务场景中常见的菜单、组织架构等树型数据结构的处理,避免代码中出现相似代码和复杂代码,采用迭代器模式,设计一套树迭代器,支持业务场景中常用的前序遍历、后序遍历和层级遍历。

2、UML图

3、使用demo

1、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 TreeIterator implements 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 TreeLevelIterator extends 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 TreePostIterator extends 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 TreePreIterator extends 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
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/969762.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号