這篇文章主要介紹了js如何構(gòu)建二叉樹進(jìn)行數(shù)值數(shù)組的去重與優(yōu)化，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

10年積累的成都網(wǎng)站建設(shè)、成都做網(wǎng)站經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先建設(shè)網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有吳江免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

常見兩層循環(huán)實(shí)現(xiàn)數(shù)組去重

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)

構(gòu)建二叉樹實(shí)現(xiàn)去重（僅適用于數(shù)值類型的數(shù)組）

將先前遍歷過的元素，構(gòu)建成二叉樹，樹中每個(gè)結(jié)點(diǎn)都滿足：左子結(jié)點(diǎn)的值 < 當(dāng)前結(jié)點(diǎn)的值 < 右子結(jié)點(diǎn)的值

這樣優(yōu)化了判斷元素是否之前出現(xiàn)過的過程

若元素比當(dāng)前結(jié)點(diǎn)大，只需要判斷元素是否在結(jié)點(diǎn)的右子樹中出現(xiàn)過即可

若元素比當(dāng)前結(jié)點(diǎn)小，只需要判斷元素是否在結(jié)點(diǎn)的左子樹中出現(xiàn)過即可

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)

優(yōu)化思路一，記錄大最小值

記錄已經(jīng)插入元素的大最小值，若比大元素大，或最小元素小，則直接插入

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)

優(yōu)化思路二，構(gòu)建紅黑樹

構(gòu)建紅黑樹，平衡樹的高度

有關(guān)紅黑樹的部分，請(qǐng)見紅黑樹的插入

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
   }
  }
  // 調(diào)整樹的結(jié)構(gòu)
  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 對(duì)象去重

[...new Set(arr)]

通過 sort() + reduce() 方法去重

排序后比較相鄰元素是否相同，若不同則添加至返回的數(shù)組中

值得注意的是，排序的時(shí)候，默認(rèn) compare(2, '2') 返回 0；而 reduce() 時(shí)，進(jìn)行全等比較

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
}, [])

通過對(duì)象的鍵值對(duì) + JSON 對(duì)象方法去重

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)))

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“js如何構(gòu)建二叉樹進(jìn)行數(shù)值數(shù)組的去重與優(yōu)化”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司，關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、網(wǎng)站設(shè)計(jì)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站題目：js如何構(gòu)建二叉樹進(jìn)行數(shù)值數(shù)組的去重與優(yōu)化-創(chuàng)新互聯(lián)
瀏覽路徑：http://weahome.cn/article/dgcegh.html