JS 實(shí)現(xiàn) 二叉樹

Yu_Huang 發(fā)布于2019-08-21 17:34 / 730人閱讀

摘要：二叉樹定義二叉排序樹二叉平衡樹二叉樹定義二叉樹是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支不存在分支度大于的節(jié)點(diǎn)的樹結(jié)構(gòu)。通常分支被稱為左子樹和右子樹。二叉樹的分支具有左右次序，不能顛倒。

① 二叉樹定義
② 二叉排序樹
③ 二叉平衡樹

① 二叉樹定義

二叉樹（Binary tree）是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支(不存在分支度大于2的節(jié)點(diǎn))的樹結(jié)構(gòu)。通常分支被稱為「左子樹」和「右子樹」。二叉樹的分支具有左右次序，不能顛倒。

② 二叉排序樹

簡單定義
二叉排序樹又稱為二叉搜索樹或二叉查找樹
特征
(1) 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值
(2) 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
(3) 它的左、右子樹也分別為二叉查找樹
Javascript實(shí)現(xiàn)

function BinarySearchTree(keys){
  //Node構(gòu)造函數(shù)
  let Node = function (key){
     this.key = key
     this.left = null
     this.right = null
  }
  let root = null
  let insertNode = (node,newNode)=>{
     if(newNode.key < node.key){
       if(node.left === null){
         node.left = newNode
       }else {
         insertNode(node.left,newNode)
       }
     }else {
       if (node.right === null) {
         node.right = newNode
       }else {
         insertNode(node.right,newNode)
       }
     }
  }
  this.insert = (key)=>{
     let newNode = new Node(key)
     if (root === null) {
       root = newNode
     }else {
       insertNode(root,newNode)
     }
  }
  keys.forEach((key)=>{
   this.insert(key)
  })
  return root
}
const keys = [8,3,10,1,6,14,4,7,13]
BinarySearchTree(keys)

chrome中打印如下：

效果圖：

中序遍歷
中序遍歷的遞歸定義：先左子樹，后根節(jié)點(diǎn)，再右子樹

let inOrderTraverseFunction =(node,cb)=>{
   if(node!==null){
      inOrderTraverseFunction(node.left,cb)
      cb(node.key)
      inOrderTraverseFunction(node.right,cb)
   }
} 
let callback =(key)=>{
  console.log(key)
}
//BST的中序遍歷
inOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome中打印如下：

結(jié)果：整顆二叉樹節(jié)點(diǎn)以從小到大依次顯示

前序遍歷
前序遍歷的遞歸定義：先根節(jié)點(diǎn)，后左子樹，再右子樹

let preOrderTraverseFunction =(node,cb)=>{
   if(node!==null){
      cb(node.key)
      preOrderTraverseFunction(node.left,cb)
      preOrderTraverseFunction(node.right,cb)
   }
} 
//BST前序遍歷
preOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome打印如下

后序遍歷
后序遍歷的遞歸定義：先左子樹，后右子樹，再根節(jié)點(diǎn)

let postOrderTraverseFunction =(node,cb)=>{
   if(node!==null){
      postOrderTraverseFunction(node.left,cb)
      postOrderTraverseFunction(node.right,cb)
      cb(node.key)
   }
} 
//BST后序遍歷
postOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome打印如下

查找BST最小值
白話:即二叉樹左子樹最左側(cè)的那個(gè)沒有左子樹的節(jié)點(diǎn)

let minNode =(node)=>{
  if(node){
    while (node&&node.left !== null){
       node = node.left
    }
    return node.key
  }
  return null
}
//查找BST最小值
console.log("the min node is "+minNode(BinarySearchTree(keys)))

chrome打印如下

查找BST最大值
白話:即二叉樹右子樹最右側(cè)的那個(gè)沒有右子樹的節(jié)點(diǎn)

let maxNode =(node)=>{
  if(node){
    while (node&&node.right !== null){
       node = node.right
    }
    return node.key
  }
  return null
}
//查找BST最大值
console.log("the max node is "+maxNode(BinarySearchTree(keys)))

chrome打印如下

查找BST某個(gè)值
即將該值和每個(gè)節(jié)點(diǎn)比較如果該值比此節(jié)點(diǎn)小則進(jìn)入左子樹再遞歸比較反之如果該值比此節(jié)點(diǎn)大則進(jìn)入右子樹再遞歸比較

let searchNode = (node,key)=>{
  if(node === null){
    return false   
  }
  if(keynode.key) {
    return searchNode(node.right,key)
  }else{
    return true
  }
}
//BST查找某個(gè)值
console.log(searchNode(BinarySearchTree(keys),3)?"node 3 is found":"node 3 is not found")
console.log(searchNode(BinarySearchTree(keys),5)?"node 5 is found":"node 5 is not found")

chrome打印如下:

刪除BST某個(gè)葉子節(jié)點(diǎn)
葉子節(jié)點(diǎn)：沒有左子樹和右子樹的節(jié)點(diǎn)

let removeNode = (node,key)=>{
  if(node === null){
    return null
  }
  if(keynode.key){
    node.right = removeNode(node.right,key)
    return node
  } else{
    if(node.left === null && node.right === null){
      node = null
      return node
    }
  }
}
//BST刪除某個(gè)葉子節(jié)點(diǎn)
console.log(removeNode(BinarySearchTree(keys),1),BinarySearchTree(keys))

chrome打印如下:

效果圖：

刪除BST某個(gè)度為1的節(jié)點(diǎn)

let removeNode = (node,key)=>{
  if(node === null){
    return null
  }
  if(keynode.key){
    node.right = removeNode(node.right,key)
    return node
  } else{
    if(node.left === null && node.right === null){
      node = null
      return node
    }
    if(node.left === null){
      node = node.right
      return node
    }else if (node.right === null) {
      node = node.left
      return node     
    }
  }
}
//BST刪除某個(gè)度為1的子節(jié)點(diǎn)
console.log(removeNode(BinarySearchTree(keys),10),BinarySearchTree(keys))

chrome打印如下:

效果圖：

刪除BST某個(gè)度為2的節(jié)點(diǎn)

let findMinNode = (node) =>{
  if(node){
    while(node&& node.left !== null){
      node = node.left
    }
    return node 
  }
  return null
}
let removeNode = (node,key)=>{
  if(node === null){
    return null
  }
  if(keynode.key){
    node.right = removeNode(node.right,key)
    return node
  } else{
    if(node.left === null && node.right === null){
      node = null
      return node
    }
    if(node.left === null){
      node = node.right
      return node
    }else if (node.right === null) {
      node = node.left
      return node     
    }
    let minNode = findMinNode(node.right) 
    node.key = minNode.key
    node.right = removeNode(node.right,minNode.key)
    return node
  }
}
//BST刪除某個(gè)度為2的子節(jié)點(diǎn)
console.log(removeNode(BinarySearchTree(keys),3),BinarySearchTree(keys))

chrome打印如下:

效果圖：

未完待續(xù)

云服務(wù)器 GPU云服務(wù)器實(shí)現(xiàn)二叉樹 JS二叉樹遍歷 js怎么建二叉樹二叉樹

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/89704.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Yu_Huang

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

lenet

閱讀 1720·2023-04-26 02:30
icejs 2.0 發(fā)布、Kraken 0.9.0 發(fā)布 | 淘系前端架構(gòu)周刊 211108 期

閱讀 1049·2021-11-10 11:36
DiyVM：十月特惠5折起，香港VPS/日本VPS/美國VPS，2G內(nèi)存套餐月付50元起,CN2線路

閱讀 1396·2021-10-08 10:14
七，F(xiàn)reeRTOS之——隊(duì)列同步與互斥

閱讀 3522·2021-09-28 09:35
pacificrack，便宜vps秋季促銷，$18/年，2核/4G內(nèi)存/50gSSD/5T流量/1G

閱讀 1562·2021-08-23 09:47
解決html頁面展開內(nèi)容出現(xiàn)滾動(dòng)條時(shí)抖動(dòng)問題

閱讀 2561·2019-08-30 15:56
前端面試每日 3+1 —— 第125天

閱讀 1483·2019-08-30 15:44
使用自定義的鼠標(biāo)圖標(biāo) --- cursor url

閱讀 1774·2019-08-30 13:59

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

JS 實(shí)現(xiàn) 二叉樹

相關(guān)文章

js數(shù)據(jù)結(jié)構(gòu)和算法（三）二叉樹

**js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))**

用JS實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)----排序二叉樹

**js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉搜索樹）**

二叉樹的遞歸遍歷（JS實(shí)現(xiàn)）

二叉樹js的生成

發(fā)表評(píng)論

0條評(píng)論

Yu_Huang

男|高級(jí)講師

TA的文章

lenet

icejs 2.0 發(fā)布、Kraken 0.9.0 發(fā)布 | 淘系前端架構(gòu)周刊 211108 期

DiyVM：十月特惠5折起，香港VPS/日本VPS/美國VPS，2G內(nèi)存套餐月付50元起,CN2線路

七，F(xiàn)reeRTOS之——隊(duì)列同步與互斥

pacificrack，便宜vps秋季促銷，$18/年，2核/4G內(nèi)存/50gSSD/5T流量/1G

解決html頁面展開內(nèi)容出現(xiàn)滾動(dòng)條時(shí)抖動(dòng)問題

前端面試每日 3+1 —— 第125天

使用自定義的鼠標(biāo)圖標(biāo) --- cursor url

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

JS 實(shí)現(xiàn) 二叉樹

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！