`

字典树相关代码

阅读更多
package com.myway.study;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 字典树 城市相关查询 (现针对26个英文字母)
 * User: zhangyong
 * Date: 14-8-10
 * Time: 上午11:21
 * To change this template use File | Settings | File Templates.
 */
public class DictionaryTree {

    private static char SPACE = ' ';

    private static char[] BASE_CHARS = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

    private TrieNode root = null;

    public DictionaryTree() {
        root = new TrieNode(SPACE);
    }

    public class TrieNode {

        private TrieNode[] childrenNodes = null;

        private char charValue;

        private boolean wordEnd = false;

        public TrieNode(char charValue) {
            this.charValue = charValue;
            childrenNodes = new TrieNode[26];
        }

        public void setWordEnd(boolean wordEnd) {
            this.wordEnd = wordEnd;
        }

        public boolean isWordEnd() {
            return wordEnd;
        }
    }

    public void insert(String word) {
        char[] charArray = word.toCharArray();
        TrieNode currentNode = root;
        for (char temp : charArray) {
            int index = (temp - 'a');
            TrieNode trieNode = currentNode.childrenNodes[index];
            if (trieNode == null) {
                trieNode = new TrieNode(temp);
                currentNode.childrenNodes[index] = trieNode;
            }
            currentNode = trieNode;
        }
        currentNode.setWordEnd(true);                                 //是一个单词
    }

    public boolean search(String key) {
        boolean flag = true;
        char[] charArray = key.toCharArray();
        TrieNode currentNode = root;
        for (char temp : charArray) {
            int index = (temp - 'a');
            TrieNode trieNode = currentNode.childrenNodes[index];
            if (trieNode == null) {
                flag = false;
                break;
            } else {
                currentNode = trieNode;
            }
        }
        return flag;
    }

    public Set<String> travel(String key) {
        char[] charArray = key.toCharArray();
        TrieNode currentNode = root;
        boolean flag = true;
        for (char temp : charArray) {
            int index = (temp - 'a');
            TrieNode trieNode = currentNode.childrenNodes[index];
            if (trieNode == null) {
                flag = false;
                break;
            } else {
                currentNode = trieNode;
            }
        }
        if (flag) {
            Set<String> set = new HashSet<String>();
            TrieNode[] childrenNodes = currentNode.childrenNodes;
            for (TrieNode child : childrenNodes) {
                if (child != null) {
                    Recursion(child, key, set);
                }
            }
            return set;
        }
        return null;
    }

    public void Recursion(TrieNode trieNode, String append, Set<String> set) {
        TrieNode currentNode = trieNode;
        if (currentNode != null) {
            String temp = append + currentNode.charValue;
            if (currentNode.isWordEnd()) {
                set.add(temp);
            }
            TrieNode[] childrenNodes = currentNode.childrenNodes;
            for (TrieNode child : childrenNodes) {
                if (child != null) {
                    Recursion(child, temp, set);
                }
            }
        }
    }

    public static void main(String[] args) {
        //比如查询 b 输出 beijing beidaihe  baoding
        DictionaryTree dictionaryTree = new DictionaryTree();
        dictionaryTree.insert("shanghai");
        dictionaryTree.insert("shenzhen");
        dictionaryTree.insert("beijing");
        dictionaryTree.insert("beidaihe");
        dictionaryTree.insert("baoding");
        dictionaryTree.insert("guangzhou");
        dictionaryTree.insert("hangzhou");
        System.out.println(dictionaryTree.search("beijing"));
        System.out.println(dictionaryTree.travel("b"));
        System.out.println(dictionaryTree.travel("guang"));
    }


}


分享到:
评论

相关推荐

    字典树_字典树_

    字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的...通过阅读和理解提供的"字典树"代码,你可以深入学习字典树的具体实现细节,包括节点的定义、插入和查找算法的实现,以及如何处理不同字符集的问题。

    字典树代码

    给出的C++代码实现了字典树的基本功能,包括节点创建、字符串插入和搜索。其中: 1. `createNew()`函数负责创建一个新的节点,并初始化其子节点指针数组和计数器。 2. `Insert_str()`函数实现字符串的插入,通过...

    字典树~java语言

    在这个"trim"压缩包文件中,可能包含了一个用Java实现字典树的项目或代码示例。你可以解压后查看源码,了解如何将上述理论知识应用到实际编程中。同时,学习如何读取文件、构建字典树,以及执行插入、搜索和删除操作...

    acm 算法 字典树模板

    ACM 算法字典树模板 在算法竞赛中,字典树(Trie)是一种常用的数据结构,用于解决字符串匹配问题。下面是字典树的基本概念和实现细节。 字典树的基本概念 字典树是一种树形数据结构,用于存储字符串集合。它的每...

    字典树php实现

    在给定的代码片段中,字典树的实现主要由两个类构成:`TrieNode` 和 `TrieTree`。接下来将对这两个类进行详细解析。 ##### 3.1 TrieNode 类 `TrieNode` 类定义了字典树中的节点结构,包含以下属性和方法: - **...

    字典树KMP优先队列

    在IT领域,字典树(Trie)是一种高效的数据结构,用于存储字符串集合。它能够快速地进行前缀查找、插入和删除操作。字典树的每个节点代表一个字符串的前缀,根节点代表空字符串,每个节点的子节点对应一个字符,节点...

    字典树简单实现

    自己写的字典树简单实现代码,实现了插入和查找功能。

    可变长数组和字典树

    在编程领域,可变长数组(也称为动态数组)和字典树(又称Trie树或前缀树)是两种非常重要的数据结构。它们在不同的场景下有着广泛的应用,尤其在处理大量数据时能展现出高效的性能。 首先,我们来详细讨论可变长...

    Java实现字典树TrieTree

    在计算机科学中,字典树(也称为前缀树或TrieTree)是一种高效的数据结构,主要用于存储字符串集合。它能够快速地进行关键词查找、插入和删除操作,尤其适合于处理大量的词汇数据,如在四六级英语考试的高频词汇查询...

    字典树_英汉词典

    ### 字典树(Trie Tree)相关知识点 #### 一、什么是字典树? 字典树,也称为前缀树或Trie树,是一种用于存储字符串的高效数据结构。它利用了字符串之间的公共前缀来减少存储空间的需求,并且能够快速进行插入、...

    字典树实例--java实现

    通过阅读和理解这段代码,你可以更深入地了解字典树的内部运作机制,并且可以将其应用于实际项目,如搜索引擎的关键词检索、IP地址解析等场景。 总之,字典树是一种高效的数据结构,尤其适用于处理大量字符串数据。...

    C语言字典树创建和搜索示例

    在计算机科学中,字典树(也称为Trie或前缀树)是一种高效的数据结构,尤其适用于快速查找和插入字符串。在C语言中实现字典树可以帮助我们构建一个高效的字符串处理程序,例如搜索引擎或者自动补全功能。在这个示例...

    c++字典树实现的 词典(课程设计)

    在本课程设计中,我们将深入探讨C++编程语言如何实现字典树,也称为Trie。字典树是一种高效的数据结构,特别适用于处理字符串查询,如查找、插入和删除单词。这种数据结构允许我们快速地搜索一个单词是否存在于词汇...

    字典树python算法.rar

    在IT领域,特别是编程和数据结构中,"字典树"是一种非常重要的数据结构,它在处理字符串相关的问题时表现出高效性。在这个“字典树python算法.rar”压缩包中,我们关注的是如何使用Python实现字典树算法。Python作为...

    字典树(Trie)的基本使用

    在"DemoNumberTrie"这个压缩包中,可能包含了一个演示如何实现和使用字典树的代码示例,可能包括以下功能: 1. **插入操作**:将一个字符串插入到字典树中。这涉及到遍历字符串的每个字符,并在树中创建或更新相应...

    字典树实现AC自动机

    它结合了字典树(Trie树)的数据结构,能够一次性查找多个模式串在文本中的出现情况。接下来,我们将深入探讨AC自动机的工作原理、实现方法以及它与字典树的关系。 **AC自动机的基本概念** AC自动机是由Aho和...

    字典树练习 POJ 1056

    总结来说,解决“字典树练习 POJ 1056”可能需要深入理解字典树的数据结构,实现插入和查询操作,并在Java环境中编写和测试代码。对于初学者,这是一次很好的机会来提高数据结构和算法的应用能力。

    AVL树/B树/红黑树/二叉搜索树/并查集/哈夫曼树/字典树实现合集(C++)

    本文将深入探讨几种重要的数据结构,包括AVL树、B树、红黑树、二叉搜索树、并查集、哈夫曼树和字典树,并概述它们的实现原理和应用场景。 首先,我们来看**AVL树**,它是一种自平衡的二叉搜索树。在AVL树中,任意...

    DT_字典树前缀推荐_源码

    在“DT_字典树前缀推荐_源码”中,我们可以推断出该压缩包包含了一套用于实现前缀推荐的源代码。这种推荐系统通常的工作流程是: 1. **构建字典树**:首先,我们需要从给定的数据集(例如,用户历史搜索记录或商品...

Global site tag (gtag.js) - Google Analytics