[移动开发]【Java】多叉树全路径遍历/TireTree实现模糊查找

import java.util.*;

/**
 * ClassName: TireTree
 * Author:Daniel
 * Date 2022/3/26
 * Version: 1.0
 * Description: 字典查找树
 */
public class TireTree {
    /**
     * 内部节点
     */
    static class Node{
        private char data;
        /**
         * 字符降序排列，主要是方便fuzzySearch函数实现升序返回
         */
        private final TreeMap<Character, Node> nextNodes = new TreeMap<>(new Comparator<Character>() {
            @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<Node> 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<length;++i){
            char c = s.charAt(i);
            Node next = current.getNext(c);
            if(next == null){
                next = new Node(c);
                current.add(next);
            }
            current = next;
        }
    }

    public List<String> fuzzySearch(String s){
        Node current = root;
        StringBuilder builder;
        List<String> res = new ArrayList<>();
        if(s == null || "".equals(s)){
            builder = new StringBuilder();
        }else {
            int length = s.length();
            for(int i =0;i<length;++i){
                current = current.getNext(s.charAt(i));
                if(current == null)return null;
            }
            builder = new StringBuilder(s.substring(0,length-1));
        }
        //        List<String> res = new ArrayList<>();

        for(String sub : traversal(current)){
            res.add(builder.append(sub).toString());
            builder.deleteCharAt(builder.length()-1);
        }
        return res;
    }
    private List<String> traversal(Node root) {
        List<String> res = new ArrayList<>();
        if (root == null || root.isLeafNode()) return res;
        StringBuilder builder = new StringBuilder();
        /**
         * 本例中的两个栈均以队尾作为栈口，主要是方便实现返回升序的字典
         */
        Deque<Node> pathStack = new ArrayDeque<>();//记录已访问，但未完成遍历的节点
        Deque<Node> stack = new ArrayDeque<>();//记录未访问的节点
        Map<Node, Integer> 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_多叉树全路径遍历