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

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

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

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

1、樹

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

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

一個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)

2、二叉樹

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

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

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

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

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

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

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

二叉樹有一個(gè)父節(jié)點(diǎn)和左右兩個(gè)子節(jié)點(diǎn)；

每個(gè)節(jié)點(diǎn)有一個(gè)值，稱為節(jié)點(diǎn)值；

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

明白了這三點(diǎn)，我們就可以開始寫代碼了

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

3.1 創(chuàng)建一個(gè)二叉樹對(duì)象

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

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

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

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

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

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

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

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

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

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

感謝你的閱讀

完整代碼：

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

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

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

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

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

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

登陸后可評(píng)論

0條評(píng)論

shengguo

男|高級(jí)講師

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

TA的文章

tomcat https

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

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

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

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

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

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

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

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

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

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(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)是怎樣的？

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

JavaScript算法之二叉搜索樹

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

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

0條評(píng)論

shengguo

男|高級(jí)講師

TA的文章

tomcat https

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

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

一些問題

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

移動(dòng)端H5頁面中1px邊框的幾種解決方法

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

for 循環(huán) var 和 let

最新活動(dòng)

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章

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

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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