Trie 数据结构

更新于 2025/10/16 16:21:06

Trie 的基本操作
插入操作
删除操作
搜索操作

Trie 是一种多路搜索树，其主要用途是从一个字符串或一组字符串中检索特定的键。它使用指向字母表中每个字母的指针，以高效有序的方式存储数据。

Trie 数据结构基于字符串的公共前缀。根节点可以包含任意数量的节点，具体取决于集合中字符串的数量。字典树的根节点除了指向其子节点的指针外，不包含任何值。

字典树数据结构有三种类型：−

标准字典树
压缩字典树
后缀字典树

字典树的实际应用包括 − 自动更正、文本预测、情感分析和数据科学。

字典树的基本操作

字典树数据结构也执行与树数据结构相同的操作。它们是 −

插入
删除
查找

插入操作

在字典树中进行插入操作是一种简单的方法。字典树的根节点不包含任何值，插入操作从根节点的直接子节点开始，这些子节点充当其子节点的键。然而，我们观察到，字典树中的每个节点都代表输入字符串中的一个字符。因此，字符会被逐个添加到字典树中，而字典树中的链接则充当指向下一级节点的指针。

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
};
struct Trie {
    struct TrieNode* root;
};
struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}
void insert(struct Trie* trie, const char* key) {
    struct TrieNode* curr = trie->root;
    for (int i = 0; i < strlen(key); i++) {
        int index = key[i] - 'a';
        if (curr->children[index] == NULL) {
            curr->children[index] = createNode();
        }
        curr = curr->children[index];
    }
    curr->isEndOfWord = 1;
}

void printWords(struct TrieNode* node, char* prefix) {
    if (node->isEndOfWord) {
        printf("%s
", prefix);
    }
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            char* newPrefix = (char*)malloc(strlen(prefix) + 2);
            strcpy(newPrefix, prefix);
            newPrefix[strlen(prefix)] = 'A' + i;
            newPrefix[strlen(prefix) + 1] = '\0';
            printWords(node->children[i], newPrefix);
            free(newPrefix);
        }
    }
}
int main() {
    struct Trie car;
    car.root = createNode();
    insert(&car, "lamborghini");
    insert(&car, "mercedes-Benz");
    insert(&car, "land Rover");
    insert(&car, "maruti Suzuki");
    printf("Trie elements are:
");
    printWords(car.root, "");
    return 0;
}

输出

Trie elements are:
LAMBORGHINI
LANDNOVER
MARUTIOUZUKI
MERCEZENZ

#include <iostream>
#include <unordered_map>
#include <string>
class TrieNode {
public:
   std::unordered_map<char, TrieNode*> children;
   bool isEndOfWord;
   
   TrieNode() {
      isEndOfWord = false;
   }
};
class Trie {
private:
    TrieNode* root;
public:
   Trie() {
      root = new TrieNode();
   }
   void insert(std::string word) {
      TrieNode* curr = root;
      for (char ch : word) {
         if (curr->children.find(ch) == curr->children.end()) {
            curr->children[ch] = new TrieNode();
         }
         curr = curr->children[ch];
      }
      curr->isEndOfWord = true;
   }
   TrieNode* getRoot() {
       return root;
   }
};

void printWords(TrieNode* node, std::string prefix) {
   if (node->isEndOfWord) {
       std::cout << prefix << std::endl;
   }
   for (auto entry : node->children) {
       printWords(entry.second, prefix + entry.first);
   }
}
int main() {
   Trie car;
   car.insert("Lamborghini");
   car.insert("Mercedes-Benz");
   car.insert("Land Rover");
   car.insert("Maruti Suzuki");
   std::cout << "Tries elements are: " << std::endl;
   printWords(car.getRoot(), "");
   return 0;
}

输出

Tries elements are: 
Maruti Suzuki
Mercedes-Benz
Land Rover
Lamborghini

import java.util.HashMap;
import java.util.Map;
class TrieNode {
   Map<Character, TrieNode> children;
   boolean isEndOfWord;
   TrieNode() {
       children = new HashMap<>();
       isEndOfWord = false;
   }
}
class Trie {
   private TrieNode root;
   Trie() {
      root = new TrieNode();
   }
   
   void insert(String word) {
      TrieNode curr = root;
      for (char ch : word.toCharArray()) {
          curr.children.putIfAbsent(ch, new TrieNode());
          curr = curr.children.get(ch);
      }
      curr.isEndOfWord = true;
   }
   TrieNode getRoot() {
      return root;
   }
}
public class Main {
   public static void printWords(TrieNode node, String prefix) {
      if (node.isEndOfWord) {
         System.out.println(prefix);
      }
      
      for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
         printWords(entry.getValue(), prefix + entry.getKey());
      }
   }
   public static void main(String[] args) {
      Trie car = new Trie();
      // 插入元素
      car.insert("Lamborghini");
      car.insert("Mercedes-Benz");
      car.insert("Land Rover");
      car.insert("Maruti Suzuki");
      // 打印插入的对象
      System.out.print("Tries elements are: 
");
      printWords(car.getRoot(), ""); // 使用公共方法访问根
   }
}

输出

Tries elements are: 
Lamborghini
Land Rover
Maruti Suzuki
Mercedes-Benz

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            curr.children.setdefault(ch, TrieNode())
            curr = curr.children[ch]
        curr.isEndOfWord = True
    def getRoot(self):
        return self.root
def printWords(node, prefix):
    if node.isEndOfWord:
        print(prefix)
    for ch, child in node.children.items():
        printWords(child, prefix + ch)

if __name__ == '__main__':
    car = Trie()
    # 插入元素
    car.insert("Lamborghini")
    car.insert("Mercedes-Benz")
    car.insert("Land Rover")
    car.insert("Maruti Suzuki")
    # 打印插入的对象
    print("Tries elements are: ")
    printWords(car.getRoot(), "")

输出

Tries elements are: 
Lamborghini
Land Rover
Mercedes-Benz
Maruti Suzuki

删除操作

字典树中的删除操作采用自下而上的方法。在字典树中搜索元素，如果找到则删除。但是，执行删除操作时需要注意一些特殊情况。

情况 1 − 键是唯一的 − 在这种情况下，整个键路径都会从节点中删除。（唯一键表示没有其他路径从一条路径分支出来）。

情况 2 − 键不唯一 − 则更新叶节点。例如，如果要删除的键是 see，但它是另一个键 seethe 的前缀；我们删除 see，并将 t、h 和 e 的布尔值更改为 false。

情况 3 − 待删除的键已经有一个前缀，− 直到前缀被删除且前缀仍保留在树中为止。例如，如果待删除的键是 heart，但存在另一个键 he；因此，我们删除 a、r 和 t，直到只剩下 he。

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

//Tries 算法的删除操作的 C 代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
//定义尺寸26
#define ALPHABET_SIZE 26
struct TrieNode {
   struct TrieNode* children[ALPHABET_SIZE];
   bool isEndOfWord;
};
struct Trie {
    struct TrieNode* root;
};
struct TrieNode* createNode() {
   struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
   node->isEndOfWord = false;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      node->children[i] = NULL;
   }
   return node;
}
void insert(struct Trie* trie, const char* key) {
    struct TrieNode* curr = trie->root;
    for (int i = 0; i < strlen(key); i++) {
        int index = key[i] - 'a';
        if (curr->children[index] == NULL) {
            curr->children[index] = createNode();
        }
        curr = curr->children[index];
    }
    curr->isEndOfWord = 1;
}
bool search(struct TrieNode* root, char* word) {
   struct TrieNode* curr = root;
   for (int i = 0; word[i] != '\0'; i++) {
      int index = word[i] - 'a';
      if (curr->children[index] == NULL) {
         return false;
      }
      curr = curr->children[index];
   }
   return (curr != NULL && curr->isEndOfWord);
}
bool startsWith(struct TrieNode* root, char* prefix) {
   struct TrieNode* curr = root;
   for (int i = 0; prefix[i] != '\0'; i++) {
      int index = prefix[i] - 'a';
      if (curr->children[index] == NULL) {
         return false;
      }
      curr = curr->children[index];
   }
   return true;
}
bool deleteWord(struct TrieNode* root, char* word) {
   struct TrieNode* curr = root;
   struct TrieNode* parent = NULL;
   int index;
   for (int i = 0; word[i] != '\0'; i++) {
      index = word[i] - 'a';
      if (curr->children[index] == NULL) {
          return false; // Trie 中不存在该词
      }
      parent = curr;
      curr = curr->children[index];
   }
   if (!curr->isEndOfWord) {
      return false; // Trie 中不存在该词
   }
   curr->isEndOfWord = false; // 标记为已删除
   if (parent != NULL) {
      parent->children[index] = NULL; // 删除子节点
   }
   return true;
}
void printWords(struct TrieNode* node, char* prefix) {
    if (node->isEndOfWord) {
        printf("%s
", prefix);
    }
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            char* newPrefix = (char*)malloc(strlen(prefix) + 2);
            strcpy(newPrefix, prefix);
            newPrefix[strlen(prefix)] = 'a' + i;
            newPrefix[strlen(prefix) + 1] = '\0';
            printWords(node->children[i], newPrefix);
            free(newPrefix);
        }
    }
}
int main() {
    struct Trie car;
    car.root = createNode();
    insert(&car, "lamborghini");
    insert(&car, "mercedes-Benz");
    insert(&car, "landrover");
    insert(&car, "maruti Suzuki");
   //删除前
   printf("删除之前尝试元素：
");
   printWords(car.root, "");
   //Deleting the elements
   char* s1  = "lamborghini";
   char* s2 = "landrover";
   printf("要删除的元素有： %s and %s", s1, s2);
   deleteWord(car.root, s1);
   deleteWord(car.root, s2);
   //删除后
   printf("
删除之前尝试元素：
");
   printWords(car.root, "");
}

输出

删除之前尝试元素：
lamborghini
landrover
marutiouzuki
mercezenz
要删除的元素有： lamborghini and landrover
删除之前尝试元素：
marutiouzuki
mercezenz

//Tries 算法的删除操作的 C++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
   unordered_map<char, TrieNode*> children;
   bool isEndOfWord;
   TrieNode() {
      isEndOfWord = false;
   }
};
class Trie {
private:
   TrieNode* root;
public:
   Trie() {
      root = new TrieNode();
   }
   void insert(string word) {
      TrieNode* curr = root;
      for (char ch : word) {
         if (curr->children.find(ch) == curr->children.end()) {
            curr->children[ch] = new TrieNode();
         }
         curr = curr->children[ch];
      }
      curr->isEndOfWord = true;
   }
TrieNode* getRoot() {
       return root;
    }
    bool deleteWord(string word) {
       return deleteHelper(root, word, 0);
    }
private:
   bool deleteHelper(TrieNode* curr, string word, int index) {
      if (index == word.length()) {
         if (!curr->isEndOfWord) {
             return false; // Trie 中不存在该词
         }
         curr->isEndOfWord = false; // 标记为已删除
         return curr->children.empty(); // 如果没有更多子项，则返回 true
      }
      char ch = word[index];
      if (curr->children.find(ch) == curr->children.end()) {
         return false; // Trie 中不存在该词
      }
      TrieNode* child = curr->children[ch];
      bool shouldDeleteChild = deleteHelper(child, word, index + 1);
      
      if (shouldDeleteChild) {
         curr->children.erase(ch); // 必要时删除子节点
         return curr->children.empty(); // 如果没有更多子项，则返回 true
      }
      return false;
   }
};
void printWords(TrieNode* node, std::string prefix) {
   if (node->isEndOfWord) {
      std::cout << prefix << std::endl;
   }
   for (auto entry : node->children) {
      printWords(entry.second, prefix + entry.first);
   }
}
int main() {
   Trie car;
   //插入元素
   car.insert("Lamborghini");
   car.insert("Mercedes-Benz");
   car.insert("Land Rover");
   car.insert("Maruti Suzuki");
   //删除前
   cout <<"删除之前尝试元素：
";
   printWords(car.getRoot(), "");
   //使用删除操作删除元素
   string s1 = "Lamborghini";
   string s2 = "Land Rover";
   cout<<"要删除的元素有： 
"<<s1<<" and "<<s2;
   car.deleteWord("Lamborghini");
   car.deleteWord("Land Rover");
   //删除后
   cout << "
删除后尝试元素：
";
   printWords(car.getRoot(), "");
}

输出

删除之前尝试元素：
Maruti Suzuki
Mercedes-Benz
Land Rover
Lamborghini
要删除的元素有： 
Lamborghini and Land Rover
删除后尝试元素：
Maruti Suzuki
Mercedes-Benz

//Tries 算法的删除操作的 Java 代码
import java.util.HashMap;
import java.util.Map;
class TrieNode {
   Map<Character, TrieNode> children;
   boolean isEndOfWord;
   
   TrieNode() {
      children = new HashMap<>();
      isEndOfWord = false;
   }
}
class Trie {
   private TrieNode root;
   Trie() {
      root = new TrieNode();
   }
   void insert(String word) {
      TrieNode curr = root;
      for (char ch : word.toCharArray()) {
         curr.children.putIfAbsent(ch, new TrieNode());
         curr = curr.children.get(ch);
      }
      curr.isEndOfWord = true;
   }
   TrieNode getRoot() {
      return root;
   }
   boolean delete(String word) {
      return deleteHelper(root, word, 0);
   }
   private boolean deleteHelper(TrieNode curr, String word, int index) {
      if (index == word.length()) {
         if (!curr.isEndOfWord) {
             return false; // Trie 中不存在该词
         }
         curr.isEndOfWord = false; // 标记为已删除
         return curr.children.isEmpty(); // 如果没有更多子项，则返回 true
      }
      char ch = word.charAt(index);
      if (!curr.children.containsKey(ch)) {
         return false; // Trie 中不存在该词
      }
      TrieNode child = curr.children.get(ch);
      boolean shouldDeleteChild = deleteHelper(child, word, index + 1);
      if (shouldDeleteChild) {
         curr.children.remove(ch); // 必要时删除子节点
         return curr.children.isEmpty(); // 如果没有更多子项，则返回 true
      }
      
      return false;
   }
}
public class Main {
   public static void printWords(TrieNode node, String prefix) {
      if (node.isEndOfWord) {
          System.out.println(prefix);
      }
      
      for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
          printWords(entry.getValue(), prefix + entry.getKey());
      }
   }
   public static void main(String[] args) {
      Trie car = new Trie(); 
      //插入元素
      car.insert("Lamborghini");
      car.insert("Mercedes-Benz");
      car.insert("Land Rover");
      car.insert("Maruti Suzuki");
      //删除前
      System.out.println("删除之前尝试元素：");
      printWords(car.getRoot(), "");
      String s1 = "Lamborghini";
      String s2 = "Land Rover";
      System.out.print("Element to be deleted are: 
" + s1 + " and " + s2);
      car.delete(s1);
      car.delete(s2);
      System.out.println("
删除后尝试元素：");
      printWords(car.getRoot(), "");
   }
}

输出

删除之前尝试元素：
Lamborghini
Land Rover
Maruti Suzuki
Mercedes-Benz
Element to be deleted are: 
Lamborghini and Land Rover
删除后尝试元素：
Maruti Suzuki
Mercedes-Benz

#python Code for Deletion operation of tries algorithm
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.isEndOfWord = True
    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.isEndOfWord
    def startsWith(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True
    def delete(self, word):
        return self.deleteHelper(self.root, word, 0)

    def deleteHelper(self, curr, word, index):
        if index == len(word):
            if not curr.isEndOfWord:
                return False  # Trie 中不存在该词
            curr.isEndOfWord = False  # 标记为已删除
            return len(curr.children) == 0  # 如果没有更多子项，则返回 true
        ch = word[index]
        if ch not in curr.children:
            return False  # Trie 中不存在该词
        child = curr.children[ch]
        shouldDeleteChild = self.deleteHelper(child, word, index + 1)
        if shouldDeleteChild:
            del curr.children[ch]  # 必要时删除子节点
            return len(curr.children) == 0  # 如果没有更多子项，则返回 true
        return False
    def getRoot(self):
        return self.root
def printWords(node, prefix):
    if node.isEndOfWord:
        print(prefix)
    for ch, child in node.children.items():
        printWords(child, prefix + ch)
trie = Trie()
插入元素
trie.insert("Lamborghini")
trie.insert("Mercedes-Benz")
trie.insert("Land Rover")
trie.insert("Maruti Suzuki")
#删除前
print("删除之前尝试元素：")
printWords(trie.getRoot(), "")
#deleting the elements using Deletion operation
s1 = "Lamborghini"
s2 = "Land Rover"
print("要删除的元素有：
",s1 ,"and",s2)
trie.delete(s1)
trie.delete(s2)
print("删除后尝试元素：")
printWords(trie.getRoot(), "")

输出

删除之前尝试元素：
Lamborghini
Land Rover
Mercedes-Benz
Maruti Suzuki
要删除的元素有：
 Lamborghini and Land Rover
删除后尝试元素：
Mercedes-Benz
Maruti Suzuki

搜索操作

在字典树中搜索是一种相当简单的方法。我们只能根据关键节点（插入操作开始的节点）向下移动字典树的层级。搜索一直进行，直到到达路径的末尾。如果找到元素，则搜索成功；否则，提示搜索失败。

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

//Tries算法的搜索操作的C程序
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
struct TrieNode {
   struct TrieNode* children[ALPHABET_SIZE];
   bool isEndOfWord;
};
struct TrieNode* createNode() {
   struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
   node->isEndOfWord = false;
   
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      node->children[i] = NULL;
   }
   return node;
}

void insert(struct TrieNode* root, char* word) {
   struct TrieNode* curr = root;
   for (int i = 0; word[i] != '\0'; i++) {
      int index = word[i] - 'a';    
      if (curr->children[index] == NULL) {
         curr->children[index] = createNode();
      }  
      curr = curr->children[index];
   } 
   curr->isEndOfWord = true;
}
bool search(struct TrieNode* root, char* word) {
   struct TrieNode* curr = root;   
   for (int i = 0; word[i] != '\0'; i++) {
      int index = word[i] - 'a';
      if (curr->children[index] == NULL) {
         return false;
      }   
      curr = curr->children[index];
   }
   return (curr != NULL && curr->isEndOfWord);
}
bool startsWith(struct TrieNode* root, char* prefix) {
   struct TrieNode* curr = root;
   for (int i = 0; prefix[i] != '\0'; i++) {
      int index = prefix[i] - 'a';  
      if (curr->children[index] == NULL) {
         return false;
      } 
      curr = curr->children[index];
   }
   return true;
}

int main() {
   struct TrieNode* root = createNode();
   //插入元素
   insert(root, "Lamborghini");
   insert(root, "Mercedes-Benz");
   insert(root, "Land Rover");
   insert(root, "Maruti Suzuki");    
   //搜索元素
   printf("Searching Cars
");
   //Printing searched elements
   printf("Found? %d
", search(root, "Lamborghini"));     // Output: 1 (true)
   printf("Found? %d
", search(root, "Mercedes-Benz"));   // Output: 1 (true)
   printf("Found? %d
", search(root, "Honda"));           // Output: 0 (false)
   printf("Found? %d
", search(root, "Land Rover"));      // Output: 1 (true)
   printf("Found? %d
", search(root, "BMW"));             // Output: 0 (false)   
   //Searching the elements the name starts with?
   printf("Cars name starts with
");
   //打印元素
   printf("Does car name starts with 'Lambo'? %d
", startsWith(root, "Lambo"));       // Output: 1 (true)
   printf("Does car name starts with 'Hon'? %d
", startsWith(root, "Hon"));         // Output: 0 (false)
   printf("Does car name starts with 'Hy'? %d
", startsWith(root, "Hy"));          // Output: 0 (false)
   printf("Does car name starts with 'Mar'? %d
", startsWith(root, "Mar"));         // Output: 1 (true)
   printf("Does car name starts with 'Land'? %d
", startsWith(root, "Land"));        // Output: 1 (true)   
   return 0;
}

输出

Searching Cars
Found? 1
Found? 1
Found? 0
Found? 1
Found? 0
Cars name starts with
Does car name starts with 'Lambo'? 1
Does car name starts with 'Hon'? 0
Does car name starts with 'Hy'? 0
Does car name starts with 'Mar'? 1
Does car name starts with 'Land'? 1

//Tries 算法的搜索操作的 C++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
   unordered_map<char, TrieNode*> children;
   bool isEndOfWord;
   
   TrieNode() {
      isEndOfWord = false;
   }
};
class Trie {
private:
    TrieNode* root;
public:
   Trie() {
      root = new TrieNode();
   }
   void insert(string word) {
      TrieNode* curr = root;
      for (char ch : word) {
         if (curr->children.find(ch) == curr->children.end()) {
            curr->children[ch] = new TrieNode();
         }
         curr = curr->children[ch];
      }
      curr->isEndOfWord = true;
   }
   TrieNode* getRoot() {
      return root;
   }
   bool search(string word) {
      TrieNode* curr = root;
      for (char ch : word) {
         if (curr->children.find(ch) == curr->children.end()) {
            return false;
         }
         curr = curr->children[ch];
      }
      return curr->isEndOfWord;
   }
   bool startsWith(string prefix) {
      TrieNode* curr = root;
      for (char ch : prefix) {
         if (curr->children.find(ch) == curr->children.end()) {
            return false;
         }
         curr = curr->children[ch];
      }
      return true;
   }
};
void printWords(TrieNode* node, std::string prefix) {
   if (node->isEndOfWord) {
      std::cout << prefix << std::endl;
   }
   for (auto entry : node->children) {
      printWords(entry.second, prefix + entry.first);
   }
}
int main() {
   Trie car;
   //插入元素
   car.insert("Lamborghini");
   car.insert("Mercedes-Benz");
   car.insert("Land Rover");
   car.insert("Maruti Suzuki");
   cout<<"Tries elements are: "<<endl;
   printWords(car.getRoot(), "");
   //搜索元素
   cout<<"Searching Cars"<< endl; 
   // 以布尔表达式打印搜索到的元素
   cout << "Found? "<<car.search("Lamborghini") << endl;     // Output: 1 (true)
   cout << "Found? "<<car.search("Mercedes-Benz") << endl;    // Output: 1 (true)
   cout << "Found? "<<car.search("Honda") << endl;     // Output: 0 (false)
   cout << "Found? "<<car.search("Land Rover") << endl;    // Output: 1 (true)
   cout << "Found? "<<car.search("BMW") << endl;   // Output: 0 (false)   
   //搜索名称以什么开头？
   cout<<"Cars name starts with" << endl;
   //打印元素
   cout << "Does car name starts with 'Lambo'? "<<car.startsWith("Lambo") << endl;   // Output: 1 (true)
   cout << "Does car name starts with 'Hon'? "<< car.startsWith("Hon") << endl;    // Output: 0 (false)
   cout << "Does car name starts with 'Hy'? "<< car.startsWith("Hy") << endl;    // Output: 0 (false)
   cout << "Does car name starts with 'Mer'? "<< car.startsWith("Mar") << endl;    // Output: 1 (true)
   cout << "Does car name starts with 'Land'? "<< car.startsWith("Land")<< endl;   // Output: 1 (true)
   return 0;
}

输出

Tries elements are: 
Maruti Suzuki
Mercedes-Benz
Land Rover
Lamborghini
Searching Cars
Found? 1
Found? 1
Found? 0
Found? 1
Found? 0
Cars name starts with
Does car name starts with 'Lambo'? 1
Does car name starts with 'Hon'? 0
Does car name starts with 'Hy'? 0
Does car name starts with 'Mer'? 1
Does car name starts with 'Land'? 1

//用于 tries 算法的 Java 程序
import java.util.HashMap;
import java.util.Map;
class TrieNode {
   Map<Character, TrieNode> children;
   boolean isEndOfWord;
   TrieNode() {
      children = new HashMap<>();
      isEndOfWord = false;
   }
}
class Trie {
   private TrieNode root;
   Trie() {
      root = new TrieNode();
   }
   void insert(String word) {
      TrieNode curr = root;
      for (char ch : word.toCharArray()) {
         curr.children.putIfAbsent(ch, new TrieNode());
         curr = curr.children.get(ch);
      }
      curr.isEndOfWord = true;
   }
TrieNode getRoot() {
   return root;
   }
   boolean search(String word) {
      TrieNode curr = root;
      for (char ch : word.toCharArray()) {
         if (!curr.children.containsKey(ch)) {
            return false;
         }
         curr = curr.children.get(ch);
      }
      return curr.isEndOfWord;
   }
   boolean startsWith(String prefix) {
      TrieNode curr = root;
      for (char ch : prefix.toCharArray()) {
         if (!curr.children.containsKey(ch)) {
            return false;
         }
         curr = curr.children.get(ch);
      }
      return true;
   }
}
public class Main {
public static void printWords(TrieNode node, String prefix) {
   if (node.isEndOfWord) {
      System.out.println(prefix);
   }
   for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
      printWords(entry.getValue(), prefix + entry.getKey());
   }
}
   public static void main(String[] args) {
      Trie car = new Trie();
      //插入元素
      car.insert("Lamborghini");
      car.insert("Mercedes-Benz");
      car.insert("Land Rover");
      car.insert("Maruti Suzuki");
      System.out.print("Tries elements are: 
");
      printWords(car.getRoot(), " ");
      //searching the elements
      System.out.println("Searching Cars");
      //Printing the searched elements
      System.out.println("Found? " + car.search("Lamborghini"));     // Output: true
      System.out.println("Found? " + car.search("Mercedes-Benz"));   // Output: true
      System.out.println("Found? " + car.search("Honda"));           // Output: false
      System.out.println("Found? " + car.search("Land Rover"));      // Output: true
      System.out.println("Found? " + car.search("BMW"));             // Output: false  
      //searching the elements name start with?
      System.out.println("Cars name starts with");
      //打印元素
      System.out.println("Does car name starts with 'Lambo'? " + car.startsWith("Lambo"));       // Output: true
      System.out.println("Does car name starts with 'Hon'? " + car.startsWith("Hon"));         // Output: false
      System.out.println("Does car name starts with 'Hy'? " + car.startsWith("Hy"));          // Output: false
      System.out.println("Does car name starts with 'Mer'? " +car.startsWith("Mar"));         // Output: true
      System.out.println("Does car name starts with 'Land'? " + car.startsWith("Land"));        // Output: true
   }
}

输出

Tries elements are: 
 Lamborghini
 Land Rover
 Maruti Suzuki
 Mercedes-Benz
Searching Cars
Found? true
Found? true
Found? false
Found? true
Found? false
Cars name starts with
Does car name starts with 'Lambo'? true
Does car name starts with 'Hon'? false
Does car name starts with 'Hy'? false
Does car name starts with 'Mer'? true
Does car name starts with 'Land'? true

#Tries 算法搜索操作的 Python 代码
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.isEndOfWord = True
    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.isEndOfWord
    def startsWith(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True
    def getRoot(self):
        return self.root
def printWords(node, prefix):
    if node.isEndOfWord:
        print(prefix)
    for ch, child in node.children.items():
        printWords(child, prefix + ch)
if __name__ == '__main__':
    car = Trie()
   插入元素
    car.insert("Lamborghini")
    car.insert("Mercedes-Benz")
    car.insert("Land Rover")
    car.insert("Maruti Suzuki")
    print("Tries elements are: ")
    printWords(car.root, " ")
    #Searching elements
    print("Searching Cars")
    #Printing the searched elements
    print("Found?",car.search("Lamborghini"))     # Output: True
    print("Found?",car.search("Mercedes-Benz"))   # Output: True
    print("Found?",car.search("Honda"))           # Output: False
    print("Found?",car.search("Land Rover"))      # Output: True
    print("Found?",car.search("BMW"))             # Output: False
    #printing elements name starts with?
    print("Cars name starts with")
    print("Does car name starts with 'Lambo'?", car.startsWith("Lambo"))       # Output: True
    print("Does car name starts with 'Hon'?",car.startsWith("Hon"))         # Output: False
    print("Does car name starts with 'Hy'?",car.startsWith("Hy"))          # Output: False
    print("Does car name starts with 'Mer'?",car.startsWith("Mer"))         # Output: True
    print("Does car name starts with 'Land'?",car.startsWith("Land"))        # Output: True

输出

Tries elements are: 
 Lamborghini
 Land Rover
 Mercedes-Benz
 Maruti Suzuki
Searching Cars
Found? True
Found? True
Found? False
Found? True
Found? False
Cars name starts with
Does car name starts with 'Lambo'? True
Does car name starts with 'Hon'? False
Does car name starts with 'Hy'? False
Does car name starts with 'Mer'? True
Does car name starts with 'Land'? True

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

Trie 数据结构

字典树的基本操作

插入操作

示例

输出

输出

输出

输出

删除操作

示例

输出

输出

输出

输出

搜索操作

示例

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！