字典树 trie

Copy 
1class TrieNode {
2  constructor(key) {
3    this.key = key;
4    this.children = [];
5  }
6}

Copy 
1class Trie {
2  constructor() {
3    this.root = new TrieNode(null);
4  }
5
6  /** 插入 */
7  insert(string) {
8    this._insert(string, this.root);
9  }
10
11  /**
12   * 插入数据到指定节点
13   * @param {string} string 数据
14   * @param {TrieNode} node 操作节点
15   */
16  _insert(string, node) {
17    if (!string) {
18      return;
19    }
20    let children = node.children;
21    let header;
22    // 遍历子节点，存在与第一个字符相等的节点赋值为 header
23    children.map(child => {
24      if (child.key === string[0]) {
25        header = child;
26      }
27    })
28    if (header) {
29      // 递归：除了第一个字符外的其他字符插入
30      this._insert(string.substring(1), header);
31    } else {
32      let node = new TrieNode(string[0])
33      if (!children.length) {
34        // 操作节点无子节点时，直接将操作节点push到子节点中
35        children.push(node);
36      } else {
37        // 否则，对比操作节点与子节点的ASCII码，按序插入到对应位置
38        let position = 0;
39        children.map(child => {
40          if (child.key < string[0]) {
41            position++;
42          }
43        })
44        children.splice(position, 0, node);
45      }
46      this._insert(string.substring(1), node);
47    }
48  }
49
50  /** 查找树中是否有string */
51  search(string) {
52    if (string === '' || !this.root.children.length) {
53      return false;
54    }
55    for (let i = 0; i < this.root.children.length; i++) {
56      if (this._search(string, this.root.children[i])) {
57        return true;
58      }
59    }
60    return false;
61  }
62
63  /**
64   * 查找某数据是否在指定节点中
65   * @param {string} string 
66   * @param {TrieNode} node 
67   */
68  _search(string, node) {
69    if (node.key !== string[0]) {
70      return false;
71    }
72    let children = node.children;
73    // 无子节点的key值与string相同
74    if (!children.length && string.length === 1) {
75      return true;
76    }
77    if (children.length > 0 && string.length > 1) {
78      // 递归查询
79      for (let i = 0; i < children.length; i++) {
80        if (children[i].key === string[1]) {
81          return this._search(string.substring(1), children[i]);
82        }
83      }
84    } else {
85      return false;
86    }
87
88  }
89
90  delete(string) {
91    if (this.search(string)) {
92      for (let i = 0; i < this.root.children.length; i++) {
93        if (this.root.children[i].key === string[0]) {
94          this._delete(string, this.root, i, string)
95          return true;
96        }
97      }
98    } else {
99      return false;
100    }
101  }
102
103  /**
104   * @param {string} string 
105   * @param {TrieNode} parent 
106   * @param {number} index 
107   * @param {string} originString 
108   */
109  _delete(string, parent, index, originString) {
110    // key值与string[0]相等的节点
111    let node = parent.children[index];
112    let children = node.children;
113    if (!children.length && string.length === 1) {
114      // string和node.key相等 且 node无子节点
115      parent.children.splice(index, 1);
116      return this.delete(originString.substring(0, originString.length - 1))
117      // this.delete(delStr.substring(0, delStr.length - 1))
118    } else if (children.length && string.length > 1) {
119      for (let i = 0; i < children.length; i++) {
120        if (children[i].key === string[1]) {
121          this._delete(string.substring(1), node, i, originString);
122          return true
123        }
124      }
125    }
126    return false;
127  }
128
129  show() {
130    this._show(this.root);
131  }
132
133  _show(node) {
134    node.children.map(child => {
135      console.log('parent: ' + node.key + '; node:', child);
136      if (child.children.length) {
137        this._show(child);
138      }
139    })
140  }
141}

Copy 
1const tree = new Trie();
2tree.insert('girl');
3tree.insert('boy');
4tree.insert('book');
5tree.insert('go');
6
7console.log(tree.search('b')); // false
8console.log(tree.search('boy')); // true
9
10tree.delete('go')
11
12console.log(tree.root);
13tree.show();