本文主要介绍了关于js构建二叉树进行数值数组的去重与优化的相关内容，分享出来供大家参考学习，下面话不多说了，来一起看看详细的介绍吧。
常见两层循环实现数组去重
let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2] let newArr = [] for (let i = 0; i < arr.length; i++) { let unique = true for (let j = 0; j < newArr.length; j++) { if (newArr[j] === arr[i]) { unique = false break } } if (unique) { newArr.push(arr[i]) } } console.log(newArr)
构建二叉树实现去重（仅适用于数值类型的数组）
将先前遍历过的元素，构建成二叉树，树中每个结点都满足：左子结点的值 < 当前结点的值 < 右子结点的值
这样优化了判断元素是否之前出现过的过程
若元素比当前结点大，只需要判断元素是否在结点的右子树中出现过即可
若元素比当前结点小，只需要判断元素是否在结点的左子树中出现过即可
let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2] class Node { constructor(value) { this.value = value this.left = null this.right = null } } class BinaryTree { constructor() { this.root = null this.arr = [] } insert(value) { let node = new Node(value) if (!this.root) { this.root = node this.arr.push(value) return this.arr } let current = this.root while (true) { if (value > current.value) { if (current.right) { current = current.right } else { current.right = node this.arr.push(value) break } } if (value < current.value) { if (current.left) { current = current.left } else { current.left = node this.arr.push(value) break } } if (value === current.value) { break } } return this.arr } } let binaryTree = new BinaryTree() for (let i = 0; i < arr.length; i++) { binaryTree.insert(arr[i]) } console.log(binaryTree.arr)
优化思路一，记录最大最小值
记录已经插入元素的最大最小值，若比最大元素大，或最小元素小，则直接插入
let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2] class Node { constructor(value) { this.value = value this.left = null this.right = null } } class BinaryTree { constructor() { this.root = null this.arr = [] this.max = null this.min = null } insert(value) { let node = new Node(value) if (!this.root) { this.root = node this.arr.push(value) this.max = value this.min = value return this.arr } if (value > this.max) { this.arr.push(value) this.max = value this.findMax().right = node return this.arr } if (value < this.min) { this.arr.push(value) this.min = value this.findMin().left = node return this.arr } let current = this.root while (true) { if (value > current.value) { if (current.right) { current = current.right } else { current.right = node this.arr.push(value) break } } if (value < current.value) { if (current.left) { current = current.left } else { current.left = node this.arr.push(value) break } } if (value === current.value) { break } } return this.arr } findMax() { let current = this.root while (current.right) { current = current.right } return current } findMin() { let current = this.root while (current.left) { current = current.left } return current } } let binaryTree = new BinaryTree() for (let i = 0; i < arr.length; i++) { binaryTree.insert(arr[i]) } console.log(binaryTree.arr)
优化思路二，构建红黑树
构建红黑树，平衡树的高度
有关红黑树的部分，请见红黑树的插入
let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2] console.log(Array.from(new Set(arr))) class Node { constructor(value) { this.value = value this.left = null this.right = null this.parent = null this.color = 'red' } } class RedBlackTree { constructor() { this.root = null this.arr = [] } insert(value) { let node = new Node(value) if (!this.root) { node.color = 'black' this.root = node this.arr.push(value) return this } let cur = this.root let inserted = false while (true) { if (value > cur.value) { if (cur.right) { cur = cur.right } else { cur.right = node this.arr.push(value) node.parent = cur inserted = true break } } if (value < cur.value) { if (cur.left) { cur = cur.left } else { cur.left = node this.arr.push(value) node.parent = cur inserted = true break } } if (value === cur.value) { break } } // 调整树的结构 if(inserted){ this.fixTree(node) } return this } fixTree(node) { if (!node.parent) { node.color = 'black' this.root = node return } if (node.parent.color === 'black') { return } let son = node let father = node.parent let grandFather = father.parent let directionFtoG = father === grandFather.left ? 'left' : 'right' let uncle = grandFather[directionFtoG === 'left' ? 'right' : 'left'] let directionStoF = son === father.left ? 'left' : 'right' if (!uncle || uncle.color === 'black') { if (directionFtoG === directionStoF) { if (grandFather.parent) { grandFather.parent[grandFather.parent.left === grandFather ? 'left' : 'right'] = father father.parent = grandFather.parent } else { this.root = father father.parent = null } father.color = 'black' grandFather.color = 'red' father[father.left === son ? 'right' : 'left'] && (father[father.left === son ? 'right' : 'left'].parent = grandFather) grandFather[grandFather.left === father ? 'left' : 'right'] = father[father.left === son ? 'right' : 'left'] father[father.left === son ? 'right' : 'left'] = grandFather grandFather.parent = father return } else { grandFather[directionFtoG] = son son.parent = grandFather son[directionFtoG] && (son[directionFtoG].parent = father) father[directionStoF] = son[directionFtoG] father.parent = son son[directionFtoG] = father this.fixTree(father) } } else { father.color = 'black' uncle.color = 'black' grandFather.color = 'red' this.fixTree(grandFather) } } } let redBlackTree = new RedBlackTree() for (let i = 0; i < arr.length; i++) { redBlackTree.insert(arr[i]) } console.log(redBlackTree.arr)
其他去重方法
通过 Set 对象去重
[...new Set(arr)]
通过 sort() + reduce() 方法去重
排序后比较相邻元素是否相同，若不同则添加至返回的数组中
值得注意的是，排序的时候，默认 compare(2, '2') 返回 0；而 reduce() 时，进行全等比较