Trie 实现中出现错误（Javascript）

Question

我正在实现 Trie 算法的 add 函数，但它给了我以下错误：

未捕获类型错误：节点不是构造函数

...在此代码行中：

node.children[char_pos]=new Array(string[0], new node());

请问，你能告诉我发生了什么事吗？

我感谢任何帮助。

这是我的代码：

var node = function(){

    this.children= new Array(26);
    this.last_char=false;
};

function add(word, node){

    char_pos=word.charCodeAt(0) - 'a'.charCodeAt(0);

    if(word.length==1){

        if(node.children[char_pos]==null){ 

            node.children[char_pos]=word[0];
            node.last_char=true;
            return;

        }else{
            return;
        };

    }else{

        if(node.children[char_pos]==null){ 
            node.children[char_pos]=new Array(word[0], new node());
        };
    };

    word=word.substring(1);
    add(word, node.children[char_pos][1]);
};

Answer 1

首先你声明

var node // = ...

然后

function add(word, node){

我想你会用节点的一些实例来调用，一个节点，而不是你的节点构造函数。

在您的函数 add 中，identifier node 解析为您的参数“node”，具有 相同标识符 的构造函数在此处不可用。 你会写

node = new node()

你会失去节点功能吗？

标准通过使用第一个大写字母命名构造函数或类（如 Node）以及 Node 的实例、node 来帮助您解决此问题，这样您就不会覆盖标识符。

事实上，您确实应该选择尚未使用的标识符，因为您将覆盖它们，并使后者不可用。

Answer 2

// we start with the TrieNode
const TrieNode = function (key) {
  // the "key" value will be the character in sequence
  this.key = key;
  
  // we keep a reference to parent
  this.parent = null;
  
  // we have hash of children
  this.children = {};
  
  // check to see if the node is at the end
  this.end = false;
  
  this.getWord = function() {
    let output = [];
    let node = this;

    while (node !== null) {
      output.unshift(node.key);
      node = node.parent;
    }

    return output.join('');
  };
}

const Trie = function() {
  this.root = new TrieNode(null);
  
  // inserts a word into the trie.
  this.insert = function(word) {
    let node = this.root; // we start at the root

    // for every character in the word
    for(let i = 0; i < word.length; i++) {
      // check to see if character node exists in children.
      if (!node.children[word[i]]) {
        // if it doesn't exist, we then create it.
        node.children[word[i]] = new TrieNode(word[i]);

        // we also assign the parent to the child node.
        node.children[word[i]].parent = node;
      }

      // proceed to the next depth in the trie.
      node = node.children[word[i]];

      // finally, we check to see if it's the last word.
      if (i == word.length-1) {
        // if it is, we set the end flag to true.
        node.end = true;
      }
    }
  };
  
  // check if it contains a whole word.
  this.search = function(word) {
    let node = this.root;

    // for every character in the word
    for(let i = 0; i < word.length; i++) {
      // check to see if character node exists in children.
      if (node.children[word[i]]) {
        // if it exists, proceed to the next depth of the trie.
        node = node.children[word[i]];
      } else {
        // doesn't exist, return false since it's not a valid word.
        return false;
      }
    }

    // we finished going through all the words, but is it a whole word?
    return node.end;
  };
  
  // returns every word with given prefix
  this.startsWith = function(prefix) {
    let node = this.root;
    let output = [];

    // for every character in the prefix
    for(let i = 0; i < prefix.length; i++) {
      // make sure prefix actually has words
      if (node.children[prefix[i]]) {
        node = node.children[prefix[i]];
      } else {
        // there's none. just return it.
        return output;
      }
    }

    // recursively find all words in the node
    findAllWords(node, output);

    return output;
  };
  
  // recursive function to find all words in the given node.
  const findAllWords = (node, arr) => {
    // base case, if node is at a word, push to output
    if (node.end) {
      arr.unshift(node.getWord());
    }

    // iterate through each children, call recursive findAllWords
    for (let child in node.children) {
      findAllWords(node.children[child], arr);
    }
  }

  // removes a word from the trie.
  this.remove = function (word) {
      let root = this.root;

      if(!word) return;

      // recursively finds and removes a word
      const removeWord = (node, word) => {

          // check if current node contains the word
          if (node.end && node.getWord() === word) {

              // check and see if node has children
              let hasChildren = Object.keys(node.children).length > 0;

              // if has children we only want to un-flag the end node that marks the end of a word.
              // this way we do not remove words that contain/include supplied word
              if (hasChildren) {
                  node.end = false;
              } else {
                  // remove word by getting parent and setting children to empty dictionary
                  node.parent.children = {};
              }

              return true;
          }

          // recursively remove word from all children
          for (let key in node.children) {
              removeWord(node.children[key], word)
          }

          return false
      };

      // call remove word on root node
      removeWord(root, word);
  };
}

干净的 JavaScript trie 实现。