JS 實現二叉樹

Yu_Huang 發布于2019-08-21 17:34 / 724人閱讀

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

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

① 二叉樹定義

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

② 二叉排序樹

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

function BinarySearchTree(keys){
  //Node構造函數
  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中打印如下：

效果圖：

中序遍歷
中序遍歷的遞歸定義：先左子樹，后根節點，再右子樹

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中打印如下：

結果：整顆二叉樹節點以從小到大依次顯示

前序遍歷
前序遍歷的遞歸定義：先根節點，后左子樹，再右子樹

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

chrome打印如下

后序遍歷
后序遍歷的遞歸定義：先左子樹，后右子樹，再根節點

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最小值
白話:即二叉樹左子樹最左側的那個沒有左子樹的節點

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最大值
白話:即二叉樹右子樹最右側的那個沒有右子樹的節點

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某個值
即將該值和每個節點比較如果該值比此節點小則進入左子樹再遞歸比較反之如果該值比此節點大則進入右子樹再遞歸比較

let searchNode = (node,key)=>{
  if(node === null){
    return false   
  }
  if(keynode.key) {
    return searchNode(node.right,key)
  }else{
    return true
  }
}
//BST查找某個值
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某個葉子節點
葉子節點：沒有左子樹和右子樹的節點

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刪除某個葉子節點
console.log(removeNode(BinarySearchTree(keys),1),BinarySearchTree(keys))

chrome打印如下:

效果圖：

刪除BST某個度為1的節點

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刪除某個度為1的子節點
console.log(removeNode(BinarySearchTree(keys),10),BinarySearchTree(keys))

chrome打印如下:

效果圖：

刪除BST某個度為2的節點

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刪除某個度為2的子節點
console.log(removeNode(BinarySearchTree(keys),3),BinarySearchTree(keys))

chrome打印如下:

效果圖：

未完待續

GPU云服務器云服務器實現二叉樹 JS二叉樹遍歷 js怎么建二叉樹二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/89704.html

js數據結構和算法（三）二叉樹

摘要：同樣結點樹的二叉樹，完全二叉樹的深度最小。二叉樹每個結點最多有兩個孩子，所以為它設計一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。二叉樹的概念二叉樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 評論0 收藏0
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現與非遞歸實現)

摘要：樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現表達式樹，在編譯器底層很有用后序遍歷可以用來實現計算目錄內的文件及其信息等。樹的簡介棧、隊列、鏈表等數據結構，都是順序數據結構。而樹是非順序數據結構。樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結...

Yuanf 2019-08-23 11:38 評論0 收藏0
用JS實現數據結構----排序二叉樹

摘要：代碼實現創建一個排序二叉樹節點類根節點插入節點以上便是創建排序二叉樹的實現方式重點在于插入節點的具體實現，即注釋的代碼片段。排序二叉樹 showImg(https://segmentfault.com/img/bVbfdbp?w=1047&h=472); 如上圖為典型的排序二叉樹，左孩子的值比節點的值小，右孩子的值比節點的值大，關于具體的樹的定義及二叉樹的定義可以百度或查閱相關資料。...

ispring 2019-08-23 11:00 評論0 收藏0
js數據結構-二叉樹（二叉搜索樹）

摘要：前言可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈表數據結構不清楚的最好先看一下本人之前寫的數據結構鏈表二叉樹二叉樹是一種樹形結構，它的特點是前言可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈...

codeKK 2019-08-23 14:34 評論0 收藏0
二叉樹的遞歸遍歷（JS實現）

摘要：本文討論二叉樹的遍歷，對節點的訪問通過打印節點的值體現出來。從二叉樹的根節點出發，遍歷可分為三個環節訪問節點打印節點的值遍歷節點的左子樹遍歷節點的右子樹不同環節執行的先后順序產生了不同的遍歷方式。至于二叉樹的非遞歸遍歷，且聽下回分解。相關概念「樹的遍歷」指按照一定規則不重復地訪問樹中所有節點的過程。「訪問」指針對節點的操作，如打印節點的值，更新節點的值等。本文討論二叉樹的遍歷，...

ethernet 2019-08-21 17:07 評論0 收藏0
二叉樹js的生成

摘要：二叉樹的生成二叉樹的概念二叉樹概念及相關操作本文是順序二叉樹及其操作的實現，非順序二叉樹應該也差不多，這里沒有實現基本二叉樹的實現添加元素查找元素刪除元素具體使用方法二叉樹的js生成二叉樹的概念二叉樹概念及相關操作本文是順序二叉樹及其操作的js實現，非順序二叉樹應該也差不多，這里沒有實現 //基本二叉樹的實現 function BT(){ this.root=null; ...

anyway 2019-08-20 14:02 評論0 收藏0