09 Implement of the data structure - Trie in ES6 JavaScript

trie.js

/* 

用JavaScript实现字典树(Trie)。
该数据结构是由节点组成的树，每个节点的数据是一个单字
每个节点拥有N个字节点，为一对多的关系

*/

// 字符节点类
class Node{

  constructor(char){
    this.char = char;
    this.parent = null;
    this.childNodes = [];
  }

  // 尝试向节点添加一个新字符节点
  add(char){
    var sameCharNode = this.get(char);
    // 如果子节点中已经有这个字符节点了，就返回这个节点
    if(sameCharNode){
      return sameCharNode;
    // 如果没有，在子节点中新增一个字符节点，并返回这个节点
    }else{
      var newNode = new Node(char);
      newNode.parent = this;
      this.childNodes.push(newNode);
      return newNode;
    }
  }

  // 在节点的子节点中找到有相同char的节点并返回
  get(char){
    var sameCharNode = this.childNodes.filter((e) => {
      return e.char == char;
    })[0];
    return sameCharNode;
  }

  // 遍历子树，异步返回所有末尾节点
  gotoEnd(callback){
    if(this.childNodes.length == 0){
      callback(this);
    }else{
      for (var i = 0; i < this.childNodes.length; i++) {
        this.childNodes[i].gotoEnd(callback);
      }
    }
  }

  // 得到所有末尾节点
  getEnds(){
    var ends = [];
    this.gotoEnd((node) => {
      ends.push(node);
    });
    return ends;
  }

  // 非递归实现查找叶子节点
  getEnds2(){
    var stack = [];
    var leafs = [];
    for (var i = 0; i < this.childNodes.length; i++) {
      var child = this.childNodes[i];
      stack.push(child);
    }
    while(stack.length > 0){
      var first = stack.shift();
      // console.log(first.char);
      if(first.childNodes.length > 0){
        for (var j = 0; j < first.childNodes.length; j++) {
          // 深度优先遍历
          stack.unshift(first.childNodes[j]);
          // 广度优先遍历
          // stack.push(first.childNodes[j]);
        }
      }else{
        leafs.push(first);
      }
    }
    return leafs;
  }
  
  // 对于末尾节点调用，向上不断找父节点，最后组合出一个完整单词
  getWord(){
    if(!this.parent){
      return this.char;
    }else{
      return this.parent.getWord() + this.char;
    }
  }
}

// 和谐词的字符节点的树类
class WordCharTree{
  // 以空字符节点为根节点
  constructor(){
    this.rootNode = new Node("");
  }
  // 向树上增加一个单词的方法
  addWord(word){
    var charArray = word.split("");
    var i = 1;
    var lastNode = this.rootNode.add(charArray[0]);
    while(i < charArray.length){
      lastNode = lastNode.add(charArray[i]);
      i++;
    }
  }
  // 树的遍历者
  traverser(){
    return new Traverser(this.rootNode);
  }
  // 公有方法
  // 使用DFA算法，用来校验一段文字有没有树中的词，返回词本身，以及其起始和结束位置
  match(text){
    var charArray = text.split("");
    var traverser = this.traverser();
    var i = 0;
    var word = "";
    var words = [];
    var start, end;
    var started = false;

    while(i < charArray.length){
      var char = charArray[i];
      var result = traverser.goto(char);
      if(result == TraverserState.START){
        started = true;
        start = i;
        word = char;
      }else if(result == TraverserState.FOUND){
        if(!started){
          started = true;
          start = i;
        }
        word += char;
      }else if(result == TraverserState.NOT_FOUND){
        if(started){
          started = false;
          end = i + 1;
        }
        word = "";
      }else if(result == TraverserState.END){
        if(started){
          started = false;
          end = i + 1;
        }
        word += char;
        words.push({word,start,end});
        word = "";
      }
      i++;
    }
    return words;
  }

  // 公有方法
  // 返回树中特定前缀的词
  startWith(suffix){
    var chars = suffix.split("");
    var words = [];    
    var i = 0;
    var startNode = this.rootNode;
    while(i < chars.length){
      startNode = startNode.get(chars[i]);
      if(!startNode){
        break;
      }
      i++;
    }
    if(!startNode) return null;
    var ends = startNode.getEnds();
    for (var i = 0; i < ends.length; i++) {
      words.push(ends[i].getWord());
    }
    return words;
  }

  // 公有方法
  // 将树转化为一个JSON字符串，方便保存至数据库
  export(){
    var output = JSON.stringify(this.rootNode);
    // TODO 压缩键名
    return output;
  }
}

// 这个是枚举类，表示遍历者的状态，只是JavaScript没有这种语法，用对象代替= =
var TraverserState = {
  START:0,
  END:1,
  FOUND:2,
  NOT_FOUND:3
};

class Traverser{
  constructor(rootNode){
    this.rootNode = rootNode;
    this.focusedNode = rootNode;
  }
  //让遍历者向下找一次的方法，会返回一个遍历者状态
  goto(char){
    var sameCharNode = this.focusedNode.get(char);
    if(sameCharNode){
      if(sameCharNode.childNodes.length == 0){
        this.focusedNode = this.rootNode;
        return TraverserState.END;
      }else{
        this.focusedNode = sameCharNode;
        return TraverserState.FOUND;
      }
    }else{
      var sameRootCharNode = this.rootNode.get(char);
      if(sameRootCharNode){
        this.focusedNode = sameRootCharNode;
        return TraverserState.START;
      }else{
        this.focusedNode = this.rootNode;
        return TraverserState.NOT_FOUND;      
      }
    }
  }
}

// 测试
var tree = new WordCharTree();
tree.addWord("satm");
tree.addWord("sato");
tree.addWord("sap");
tree.addWord("sas");
tree.addWord("sober");
tree.addWord("node");
tree.addWord("recursive");
tree.addWord("finalize");
tree.addWord("node");
tree.addWord("process");
tree.addWord("reaches");
tree.addWord("actual");
tree.addWord("most");
tree.addWord("Asynchronous");
tree.addWord("request");
tree.addWord("for");
tree.addWord("soben");
tree.addWord("sk");

var result = tree.startWith("a");
console.log(result);

// var text = "dijofawksatmsapfaojisassksksksobenajwfojkfasober";
// console.log(tree.match(text));