字典树Trie树 + 深度优先遍历DFS

╰半夏微凉° 2022-05-26 11:49 157阅读 0赞

字典树是非常常见的数据结构，一定要学会使用。

这个很棒，在做char数组的DFS遍历的时候可能会用到，

这个时一定要学会手写的代码！！！！！

C++版本如下：

class TrieNode 
    {
    public:
        // Initialize your data structure here.
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) 
        {
            for (auto &a : child)
                a = NULL;
        }
    };
    
    class Trie 
    {
    public:
        Trie() 
        {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string s)
        {
            TrieNode *p = root;
            for (auto &a : s) {
                int i = a - 'a';
                if (p->child[i]==NULL)
                    p->child[i] = new TrieNode();
                p = p->child[i];
            }
            p->isWord = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) 
        {
            TrieNode *p = root;
            for (auto &a : key) 
            {
                int i = a - 'a';
                if (p->child[i]==NULL)
                    return false;
                p = p->child[i];
            }
            return p->isWord;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix)
        {
            TrieNode *p = root;
            for (auto &a : prefix) 
            {
                int i = a - 'a';
                if (p->child[i]==NULL) 
                    return false;
                p = p->child[i];
            }
            return true;
        }
    
    private:
        TrieNode* root;
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关二分搜索树深度优先遍历

二分搜索树遍历分为两大类，深度优先遍历和层序遍历。深度优先遍历分为三种：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后

分手后的思念是犯贱/ 2024年03月16日 21:25/ 0 赞/ 42 阅读

相关树的深度搜索遍历DFS

定义：深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返

╰半夏微凉°/ 2022年12月11日 07:54/ 0 赞/ 156 阅读

相关 Trie树（字典树）

很有段时间没写此系列了，今天我们来说Trie树，Trie树的名字有很多，比如字典树，前缀树等等。一：概念下面我们有and,as,at,cn,com这些关键词，那么如何

阳光穿透心脏的1/2处/ 2022年08月14日 00:00/ 0 赞/ 261 阅读

相关树的遍历-深度优先遍历和广度优先遍历

深度优先遍历类似于树的先序遍历。假设给定初态是图中所有顶点均未被访问过，从图中某一顶点vi出发遍历图中的定义如下：首先访问出发点vi，并将其访问标志置为1；然后，从vi出发点依

电玩女神/ 2022年05月27日 07:20/ 0 赞/ 555 阅读

相关字典树Trie树 + 深度优先遍历DFS

字典树是非常常见的数据结构，一定要学会使用。这个很棒，在做char数组的DFS遍历的时候可能会用到，这个时一定要学会手写的代码！！！！！ C++版本如下：

╰半夏微凉°/ 2022年05月26日 11:49/ 0 赞/ 158 阅读

相关 Trie树——字典树

1、概述 Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。 Trie一词来自r

朴灿烈づ我的快乐病毒、/ 2022年05月21日 06:20/ 0 赞/ 306 阅读

相关 Trie树（字典树）

1. Trie树 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索

梦里梦外;/ 2022年05月17日 05:21/ 0 赞/ 231 阅读

相关二叉树遍历——深度优先(DFS)与广度优先(BFS)

二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点

我不是女神ヾ/ 2022年05月16日 12:12/ 0 赞/ 248 阅读

相关二叉树遍历——深度优先遍历、广度优先遍历

二叉树遍历简介【备注】：二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。 1. 深度优先遍历：对每一个可能的

布满荆棘的人生/ 2022年05月12日 14:40/ 0 赞/ 296 阅读

相关 DFS深度优先搜索遍历

转载：[https://blog.csdn.net/qq\_38442065/article/details/81634282][https_blog.csdn.net_qq_

悠悠/ 2021年11月22日 11:14/ 0 赞/ 390 阅读