Javascript中的8种常见数据结构( 三 ) _Javascript

这是二叉搜索树的示例。每个节点最多有两个节点，左节点小于当前节点，右节点大于当前节点：

文章插图

二进制搜索树中的常用方法：
· add：在树中插入一个节点
· findMin：获取最小节点
· findMax：获取最大节点
· find：搜索特定节点
· isPresent：确定某个节点的存在
· delete：从树中删除节点
JavaScript中的示例：
class Node { constructor(data, left = null, right = null) { this.data = https://www.isolves.com/it/cxkf/yy/js/2019-12-09/data; this.left = left; this.right = right; }}class BST { constructor() { this.root = null; } add(data) { const node = this.root; if (node === null) { this.root = new Node(data); return; } else { const searchTree = function (node) { if (data < node.data) { if (node.left === null) { node.left = new Node(data); return; } else if (node.left !== null) { return searchTree(node.left); } } else if (data > node.data) { if (node.right === null) { node.right = new Node(data); return; } else if (node.right !== null) { return searchTree(node.right); } } else { return null; } }; return searchTree(node); } } findMin() { let current = this.root; while (current.left !== null) { current = current.left; } return current.data; } findMax() { let current = this.root; while (current.right !== null) { current = current.right; } return current.data; } find(data) { let current = this.root; while (current.data !== data) { if (data < current.data) { current = current.left } else { current = current.right; } if (current === null) { return null; } } return current; } isPresent(data) { let current = this.root; while (current) { if (data === current.data) { return true; } if (data < current.data) { current = current.left; } else { current = current.right; } } return false; } remove(data) { const removeNode = function (node, data) { if (node == null) { return null; } if (data == node.data) { // no child node if (node.left == null && node.right == null) { return null; } // no left node if (node.left == null) { return node.right; } // no right node if (node.right == null) { return node.left; } // has 2 child nodes var tempNode = node.right; while (tempNode.left !== null) { tempNode = tempNode.left; } node.data = tempNode.data; node.right = removeNode(node.right, tempNode.data); return node; } else if (data < node.data) { node.left = removeNode(node.left, data); return node; } else { node.right = removeNode(node.right, data); return node; } } this.root = removeNode(this.root, data); }}测试一下：
const bst = new BST();bst.add(4);bst.add(2);bst.add(6);bst.add(1);bst.add(3);bst.add(5);bst.add(7);bst.remove(4);console.log(bst.findMin());console.log(bst.findMax());bst.remove(7);console.log(bst.findMax());console.log(bst.isPresent(4));结果：
176false7.Trie（发音为" try"）

文章插图

Trie或"前缀树"也是一种搜索树。Trie分步存储数据-树中的每个节点代表一个步骤。Trie用于存储词汇，因此可以快速搜索，尤其是自动完成功能。
Trie中的每个节点都有一个字母-在分支之后可以形成一个完整的单词。它还包含一个布尔指示符，以显示这是否是最后一个字母。
Trie具有以下方法：
· add：在字典树中插入一个单词
· isword：确定树是否由某些单词组成
· print：返回树中的所有单词
/** Node in Trie **/function Node() {this.keys = new Map();this.end = false;this.setEnd = function () {this.end = true;};this.isEnd = function () {return this.end;}}function Trie() {this.root = new Node();this.add = function (input, node = this.root) {if (input.length === 0) {node.setEnd();return;} else if (!node.keys.has(input[0])) {node.keys.set(input[0], new Node());return this.add(input.substr(1), node.keys.get(input[0]));} else {return this.add(input.substr(1), node.keys.get(input[0]));}}this.isWord = function (word) {let node = this.root;while (word.length > 1) {if (!node.keys.has(word[0])) {return false;} else {node = node.keys.get(word[0]);word = word.substr(1);}}return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;}this.print = function () {let words = new Array();let search = function (node = this.root, string) {if (node.keys.size != 0) {for (let letter of node.keys.keys()) {search(node.keys.get(letter), string.concat(letter));}if (node.isEnd()) {words.push(string);}} else {string.length > 0 ? words.push(string) : undefined;return;}};search(this.root, new String());return words.length > 0 ? words : null;}}8.图