[数据结构]01字典树实现(ts)

class Node<T> {
    value: T;
    children: Array<Node<T>>;
 
    constructor(value: T) {
        this.value = value;
        this.children = new Array<Node<T>>();
    }
}
 
class Trie<T> {
    root: Node<T>;
 
    constructor() {
        this.root = new Node<T>(null);
    }
 
    // 插入一个字符串
    insert(word: T[]) {
        if (word.length === 0) return;
        let current = this.root;
        word.forEach(char => {
            let child = current.children.find(node => node.value === char);
            if (!child) {
                child = new Node(char);
                current.children.push(child);
            }
            current = child;
        });
    }
 
    // 查询一个字符串是否存在
    search(word: T[]) {
        if (word.length === 0) return false;
        let current = this.root;
        for (let char of word) {
            let child = current.children.find(node => node.value === char);
            if (!child) return false;
            current = child;
        }
        return true;
    }
 
    // 删除一个字符串
    delete(word: T[]) {
        if (word.length === 0 || !this.search(word)) return;
        let current = this.root;
        let ancestors = new Array<Node<T>>();
        for (let char of word) {
            let child = current.children.find(node => node.value === char);
            ancestors.push(current);
            current = child;
        }
 
        // 如果当前节点有子节点，则无法删除
        if (current.children.length > 0) return;
 
        // 当前节点没有子节点，可以删除
        let parent = ancestors.pop();
        while (parent && parent.children.length === 1 && parent.value !== null) {
            current = parent;
            parent = ancestors.pop();
        }
 
        // 如果parent为null，则删除根节点，否则删除current节点
        if (parent) {
            let index = parent.children.findIndex(node => node.value === current.value);
            parent.children.splice(index, 1);
        } else {
            this.root = new Node(null);
        }
    }
}
 
// 使用示例
const trie = new Trie<string>();
trie.insert(["t", "e", "s", "t"]);
trie.insert(["t", "h", "i", "s"]);
console.log(trie.search(["t", "e", "s", "t"])); // true
console.log(trie.search(["t", "h", "i", "s"])); // true
console.log(trie.search(["t", "e", "s", "t", "e"])); // false
trie.delete(["t", "e", "s", "t"]);
console.log(trie.search(["t", "e", "s", "t"])); // false

这段代码定义了一个简单的字典树（Trie），它可以插入、查询和删除字符串。字典树通常用于搜索