Javascript 數(shù)據(jù)結(jié)構(gòu)與算法——二叉樹

shengguo 發(fā)布于2019-08-26 10:33 / 2951人閱讀

摘要：一個節(jié)點可以有多個子節(jié)點二叉樹二叉樹是一種特殊的樹，子節(jié)點數(shù)不超過個。以某種特定的順序訪問樹中所有的節(jié)點稱為樹的遍歷樹的層數(shù)稱為樹的深度一個父節(jié)點的兩個子節(jié)點分別稱為左節(jié)點和右節(jié)點二叉查找樹又稱二叉排序樹是一種特殊的二叉樹。

原文地址：http://www.brandhuang.com/article/1564967352592

1、樹

一棵樹最上面的節(jié)點：根結(jié)點

一個節(jié)點下面連接多個節(jié)點，那個這個節(jié)點稱「為父節(jié)點」，它下面的節(jié)點稱為「子節(jié)點」，沒有任何子節(jié)點的節(jié)點稱為「葉子節(jié)點」。

一個節(jié)點可以有多個子節(jié)點

2、二叉樹

二叉樹是一種特殊的樹，子節(jié)點數(shù)不超過「2個」。

以某種特定的順序訪問樹中所有的節(jié)點稱為樹的遍歷

樹的層數(shù)稱為「樹的深度」

一個父節(jié)點的兩個子節(jié)點分別稱為「左節(jié)點」和「右節(jié)點」

「二叉查找樹」（又稱二叉排序樹）是一種特殊的二叉樹。++相對較小的值保存在左節(jié)點中，相對較大的值保存在右節(jié)點中++

3、js構(gòu)建以一顆二叉樹

用代碼構(gòu)建二叉樹前，先要在腦中不斷的重復二叉樹的重要特點：

二叉樹有一個父節(jié)點和左右兩個子節(jié)點；

每個節(jié)點有一個值，稱為節(jié)點值；

左節(jié)點的值小于父節(jié)點的值，右節(jié)點的值大于父節(jié)點值。

明白了這三點，我們就可以開始寫代碼了

構(gòu)建二叉樹的完整代碼請看文末

3.1 創(chuàng)建一個二叉樹對象

創(chuàng)建一個二叉樹對象，定義一個對象來保存節(jié)點的值和其子節(jié)點

function binaryTree(){
    let Node = function (key){
        this.key = key      // 節(jié)點值
        this.left = null    // 該節(jié)點的左節(jié)點
        this.right = null   // 該節(jié)點的右節(jié)點
    }
    let root = null         // 根結(jié)點，初始值為null
}

3.2 創(chuàng)建一個構(gòu)建二叉樹的函數(shù)

在binaryTree中創(chuàng)建一個insert方法，通過insert方法向樹中添加新節(jié)點

function binaryTree(){
    let Node = function (key){
        this.key = key      // 節(jié)點值
        this.left = null    // 該節(jié)點的左節(jié)點
        this.right = null   // 該節(jié)點的右節(jié)點
    }
    let root = null         // 根結(jié)點，初始值為null
    
    
    let insertNode = function(node, newNode){
        if (newNode.key < node.key) { // 如果新節(jié)點的key值小于原來節(jié)點的key值，則該新節(jié)點作為原節(jié)點的左節(jié)點加入
        if (node.left) { // 如果原節(jié)點的左節(jié)點已經(jīng)存在，則繼續(xù)執(zhí)行insertNode方法
          insertNode(node.left, newNode)
        } else { // 如果原節(jié)點的左節(jié)點不存在，則將新節(jié)點作為原節(jié)點的左節(jié)點
          node.left = newNode
        }
      } else { // 如果新節(jié)點的key值大于原來節(jié)點的key值，則作為原節(jié)點的右節(jié)點加入
        if (node.right) {
          insertNode(node.right, newNode)
        } else {
          node.right = newNode
        }
      }
    }
    
    this.insert = function(key){
        let newNode = new Node(key)  // 插入節(jié)點時創(chuàng)建一個Node對象來保存節(jié)點的數(shù)據(jù)
      if (root) {
        insertNode(root, newNode) // 如果根結(jié)點已經(jīng)存在，則通過insertNode方法進行插入
      } else {
        root = newNode  // 如果根結(jié)點為空，則把該節(jié)點作為根結(jié)點
      }
    }
}

3.3 構(gòu)建一個二叉樹

  let nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
  let tree = new binaryTree()
  nodes.forEach(function (key) {
    tree.insert(key)
  })

至此，一個二叉樹構(gòu)建完畢

其實，只要你了解了二叉樹的三個重要特點，構(gòu)建一棵二叉樹是不是還是比較容易的呢？

可以將代碼復制到自己的文件中進行單步調(diào)試，看看執(zhí)行的結(jié)果是不是和前面描述的二叉樹的特點相同。

感謝你的閱讀

完整代碼：

function binaryTree(){
    let Node = function (key){
        this.key = key      // 節(jié)點值
        this.left = null    // 該節(jié)點的左節(jié)點
        this.right = null   // 該節(jié)點的右節(jié)點
    }
    let root = null         // 根結(jié)點，初始值為null
    
    
    let insertNode = function(node, newNode){
        if (newNode.key < node.key) { // 如果新節(jié)點的key值小于原來節(jié)點的key值，則該新節(jié)點作為原節(jié)點的左節(jié)點加入
        if (node.left) { // 如果原節(jié)點的左節(jié)點已經(jīng)存在，則繼續(xù)執(zhí)行insertNode方法
          insertNode(node.left, newNode)
        } else { // 如果原節(jié)點的左節(jié)點不存在，則將新節(jié)點作為原節(jié)點的左節(jié)點
          node.left = newNode
        }
      } else { // 如果新節(jié)點的key值大于原來節(jié)點的key值，則作為原節(jié)點的右節(jié)點加入
        if (node.right) {
          insertNode(node.right, newNode)
        } else {
          node.right = newNode
        }
      }
    }
    
    this.insert = function(key){
        let newNode = new Node(key)  // 插入節(jié)點時創(chuàng)建一個Node對象來保存節(jié)點的數(shù)據(jù)
      if (root) {
        insertNode(root, newNode) // 如果根結(jié)點已經(jīng)存在，則通過insertNode方法進行插入
      } else {
        root = newNode  // 如果根結(jié)點為空，則把該節(jié)點作為根結(jié)點
      }
    }
}

let nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
  let tree = new binaryTree()
  nodes.forEach(function (key) {
    tree.insert(key)
  })

云服務器 GPU云服務器二叉樹算法最優(yōu)二叉樹算法圖二叉樹的存儲結(jié)構(gòu) c語言二叉樹輸入數(shù)據(jù)

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

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/106375.html

發(fā)表評論

登陸后可評論

0條評論

shengguo

男|高級講師

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

TA的文章

tomcat https

閱讀 1910·2021-11-25 09:43
環(huán)境影響著一個人...最高月薪20K，想成為最優(yōu)秀的人，就要向最優(yōu)秀的人學習

閱讀 1558·2021-09-02 15:21
我們來翻翻元素樣式的族譜-getComputedStyle

閱讀 3524·2019-08-30 15:52
一些問題

閱讀 1559·2019-08-30 12:48
提升網(wǎng)站頁面速度的14條最佳實踐（二）

閱讀 1374·2019-08-30 10:57
移動端H5頁面中1px邊框的幾種解決方法

閱讀 2991·2019-08-26 17:41
JS去重的幾種實現(xiàn)方法

閱讀 743·2019-08-26 11:59
for 循環(huán) var 和 let

閱讀 1427·2019-08-26 10:41

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

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

Javascript 數(shù)據(jù)結(jié)構(gòu)與算法——二叉樹

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 非線性表中的樹、堆是干嘛用的？其數(shù)據(jù)結(jié)構(gòu)是怎樣的？

**學習*JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法（四）：二叉搜索樹**

JavaScript算法之二叉搜索樹

數(shù)據(jù)結(jié)構(gòu)與算法（樹） --javascript語言描述

發(fā)表評論

0條評論

shengguo

男|高級講師

TA的文章

tomcat https

環(huán)境影響著一個人...最高月薪20K，想成為最優(yōu)秀的人，就要向最優(yōu)秀的人學習

我們來翻翻元素樣式的族譜-getComputedStyle

一些問題

提升網(wǎng)站頁面速度的14條最佳實踐（二）

移動端H5頁面中1px邊框的幾種解決方法

JS去重的幾種實現(xiàn)方法

for 循環(huán) var 和 let

最新活動

資訊專欄INFORMATION COLUMN

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

Javascript 數(shù)據(jù)結(jié)構(gòu)與算法——二叉樹

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

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