【Java】多叉树全路径遍历/TireTree实现模糊查找

import java.util.*;


public class TireTree {
    
    static class Node{
        private char data;
        
        private final TreeMap nextNodes = new TreeMap<>(new Comparator() {
            @Override
            public int compare(Character o1, Character o2) {
                return o2-o1;
            }
        });

        public Node() {
        }

        public Node(char data) {
            this.data = data;
        }

        public void add(Node node){
            nextNodes.put(node.getData(),node);
        }

        public Node getNext(char key){
            return nextNodes.get(key);
        }

        public boolean isLeafNode(){
            return nextNodes.isEmpty();
        }

        public char getData() {
            return data;
        }
        public Collection getNextDescendingNodes(){
            return nextNodes.values();
        }
        public int size() { return nextNodes.size(); }
    }
//    ===========================================================================================================
    private final Node root = new Node();

    public TireTree() {
    }
    public TireTree(String... words){
        for(String s:words){
            this.add(s);
        }
    }
    public void add(String s){
        Node current = root;
        int length = s.length();
        for(int i =0;i fuzzySearch(String s){
        Node current = root;
        int length = s.length();
        for(int i =0;i res = new ArrayList<>();
        for(String sub : traversal(current)){
            res.add(builder.append(sub).toString());
            builder.deleteCharAt(builder.length()-1);
        }
        return res;
    }
    private List traversal(Node root) {
        List res = new ArrayList<>();
        if (root == null || root.isLeafNode()) return res;
        StringBuilder builder = new StringBuilder();
        
        Deque pathStack = new ArrayDeque<>();//记录已访问，但未完成遍历的节点
        Deque stack = new ArrayDeque<>();//记录未访问的节点
        Map popCounter = new HashMap<>();//记录访问节点的子节点次数，用来判断是否遍历完一个节点
        stack.add(root);
        for(;;) {
            //当前节点出stack,开始访问该节点
            Node current = stack.pollLast();//出栈结点为null的情况在开头已经排除，when root = null
            if(current.isLeafNode()){
                //得到一次遍历结果
                builder.append(current.getData());
                res.add(builder.toString());
                builder.deleteCharAt(builder.length()-1);
                //stack为空表明遍历结束
                if(stack.isEmpty())break;
                //回溯：删除pathStack中无法遍历的所有祖先节点
                Node father;
                for(;;){
                    father = pathStack.pollLast();//出栈结点为null的情况在开头已经排除，when root不为null但没有任何子结点
                    //father对应的counter++,若为null则置1
                    popCounter.merge(father, 1, Integer::sum);
                    if(popCounter.get(father) != father.size()){
                        pathStack.add(father);
                        break;
                    }else {
                        builder.deleteCharAt(builder.length()-1);
                    }
                }
            }else{//当前节点的所有子节点入栈stack
                stack.addAll(current.getNextDescendingNodes());//可以保证栈口的字典是较小的
                pathStack.add(current);//标记访问
                builder.append(current.getData());
            }
        }
        return res;
    }
}

多叉树 最长路径 java_多叉树全路径遍历