js构建二叉树进行数值数组的去重与优化详解

前言本文主要介绍了关于js构建二叉树进行数值数组的去重与优化的相关内容，分享出来供

前言

本文主要介绍了关于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() 时，进行全等比较

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.sort((a, b) => {
 let res = a - b
 if (res !== 0) {
 return res
 } else {
 if (a === b) {
 return 0
 } else {
 if (typeof a === 'number') {
 return -1
 } else {
 return 1
 }
 }
 }
}).reduce((pre, cur) => {
 if (pre !== cur) {
 newArr.push(cur)
 return cur
 }
 return pre
}, null)

通过 includes() + map() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

通过 includes() + reduce() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = arr.reduce((pre, cur) => {
 !pre.includes(cur) && pre.push(cur)
 return pre
}, [])

通过对象的键值对 + JSON 对象方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let obj = {}
arr.map(a => {
 if(!obj[JSON.stringify(a)]){
 obj[JSON.stringify(a)] = 1
 }
})
console.log(Object.keys(obj).map(a => JSON.parse(a)))

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对脚本之家的支持。

js 构建二叉树 二叉树 数组 js数组去重