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

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

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

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

1、樹(shù)

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

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

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

2、二叉樹(shù)

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

以某種特定的順序訪(fǎng)問(wèn)樹(shù)中所有的節(jié)點(diǎn)稱(chēng)為樹(shù)的遍歷

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

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

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

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

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

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

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

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

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

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

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

創(chuàng)建一個(gè)二叉樹(shù)對(duì)象，定義一個(gè)對(duì)象來(lái)保存節(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ù)的函數(shù)

在binaryTree中創(chuàng)建一個(gè)insert方法，通過(guò)insert方法向樹(shù)中添加新節(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值小于原來(lái)節(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值大于原來(lái)節(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ì)象來(lái)保存節(jié)點(diǎn)的數(shù)據(jù)
      if (root) {
        insertNode(root, newNode) // 如果根結(jié)點(diǎn)已經(jīng)存在，則通過(guò)insertNode方法進(jìn)行插入
      } else {
        root = newNode  // 如果根結(jié)點(diǎn)為空，則把該節(jié)點(diǎn)作為根結(jié)點(diǎn)
      }
    }
}

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

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

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

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

可以將代碼復(fù)制到自己的文件中進(jìn)行單步調(diào)試，看看執(zhí)行的結(jié)果是不是和前面描述的二叉樹(shù)的特點(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值小于原來(lái)節(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值大于原來(lái)節(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ì)象來(lái)保存節(jié)點(diǎn)的數(shù)據(jù)
      if (root) {
        insertNode(root, newNode) // 如果根結(jié)點(diǎn)已經(jīng)存在，則通過(guò)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)
  })