kyrenesjtv.github.io

https://kyrenesjtv.github.io/

---

Project maintained by kyrenesjtv Hosted on GitHub Pages — Theme by mattgraham

树的种类有很多，这里主要描述的字典树。

确定一下字典树的概念

1. 从根节点到叶节点只存在一条路
2. 每个节点的上一级跟下一级(假设存在上一级和下一级)的距离为1

那我们现在构建一下节点

package me.kyrene.demo.test;

import java.util.HashMap;

/**
 * @ProjectName: demo4Java
 * @Author: AlbertW
 * @CreateDate: 2019/1/13 20:47
 */
public class TreeNode {


    public char label;  // 结点的名称，在前缀树里是单个字母
    public HashMap<Character, TreeNode> sons = null; // 使用哈希映射存放子结点。哈希便于确认是否已经添加过某个字母对应的结点。  key是下一个字母
    public String prefix = null;   // 从树的根到当前结点这条通路上，全部字母所组成的前缀。例如通路 b->o->y，对于字母 o 结点而言，前缀是 b；对于字母 y 结点而言，前缀是 bo
    public String explanation = null;  // 词条的解释

    // 初始化结点
    public TreeNode(char l, String pre, String exp) {
        label = l;
        prefix = pre;
        explanation = exp;
        sons = new HashMap<>();

    }

    public TreeNode() {

    }

    public char getLabel() {
        return label;
    }

    public void setLabel(char label) {
        this.label = label;
    }

    public String getPrefix() {
        return prefix;
    }

    public void setPrefix(String prefix) {
        this.prefix = prefix;
    }
}

创建字典树

    /**
     * 创建字典树
     * @param rootNode 字典root
     * @param str 未收入的单词
     * @return 字典root
     */
    public static TreeNode createDictionary(TreeNode rootNode,String str){

        TreeNode treeNode = new TreeNode();
        TreeNode tempNode = rootNode;
        for(int i = 0 ; i<str.length() ; i++){
            if(tempNode.sons.containsKey(str.charAt(i))){
                //有这个子节点
                treeNode = tempNode.sons.get(str.charAt(i));
            }else {
                //没有这个子节点 则收录
                 String pre =  tempNode.getPrefix()+tempNode.getLabel();
                treeNode = new TreeNode(str.charAt(i),pre,"");
                tempNode.sons.put(str.charAt(i),treeNode);
                tempNode = treeNode;
            }

        }

        return rootNode;
    }

打印字典树叶节点

    /**
     * 深度查找字典树
     * @param node 根节点
     */
    public static void dfsByStack(TreeNode node){

        Stack<TreeNode> stack = new Stack<>();

        stack.push(node);

        while(!stack.isEmpty()){

            TreeNode currentNode = stack.pop();

            //没有子节点
            if(currentNode.sons.size() == 0){
                System.out.println(currentNode.prefix+currentNode.label);
            }else {

                //迭代
                Iterator<Map.Entry<Character, TreeNode>> iterator = currentNode.sons.entrySet().iterator();

                while(iterator.hasNext()){
                    //放入栈中。  但是顺序打印出来是跟放入的相反
                    stack.push(iterator.next().getValue());
                }
            }
        }
    }