二叉樹(shù)的順序插入

forsigner 發(fā)布于2019-08-21 17:08 / 1046人閱讀

摘要：每次插入的新節(jié)點(diǎn)都會(huì)入列。同時(shí)，若新節(jié)點(diǎn)被插入到父節(jié)點(diǎn)的右下方，則該父節(jié)點(diǎn)出列。

模擬過(guò)程

插入根節(jié)點(diǎn)A

在父節(jié)點(diǎn)A的左下方插入子節(jié)點(diǎn)B

在父節(jié)點(diǎn)A的右下方插入子節(jié)點(diǎn)C

在父節(jié)點(diǎn)B的左下方插入子節(jié)點(diǎn)D

在父節(jié)點(diǎn)B的右下方插入子節(jié)點(diǎn)E

在父節(jié)點(diǎn)C的左下方插入子節(jié)點(diǎn)F
...

分析過(guò)程

每次插入節(jié)點(diǎn)需明確被插入的父節(jié)點(diǎn)以及被插入的位置（左右）

明確被插入的父節(jié)點(diǎn)

第1步中，需將A存儲(chǔ)，因?yàn)锳在第2，3步中被取出，作為插入操作的父節(jié)點(diǎn)
第2步中，需將B存儲(chǔ)，因?yàn)锽在第4，5步中被取出，作為插入操作的父節(jié)點(diǎn)
第3步中，需將C存儲(chǔ)，因?yàn)镃在第6步中被取出，作為插入操作的父節(jié)點(diǎn)，與此同時(shí)，A在被執(zhí)行右下方的插入操作后，A不能再被插入子節(jié)點(diǎn)
...
第5步中，需將E存儲(chǔ)，其在后續(xù)的操作中會(huì)被取出，作為插入操作的父節(jié)點(diǎn)，與此同時(shí)，B與A一樣，在被執(zhí)行右下方的插入操作后，B不能再被插入子節(jié)點(diǎn)
故建個(gè)隊(duì)列，將后續(xù)操作中會(huì)被取出的節(jié)點(diǎn)存儲(chǔ)，不會(huì)再被取出的節(jié)點(diǎn)移除。每次插入的新節(jié)點(diǎn)都會(huì)入列。同時(shí)，若新節(jié)點(diǎn)被插入到父節(jié)點(diǎn)的右下方，則該父節(jié)點(diǎn)出列。

明確被插入的位置

被插入的位置可以通過(guò)插入的次數(shù)來(lái)判斷，若是第1次插入，則是根節(jié)點(diǎn)，若是第n(n>1)次插入，n為偶，則插入左邊，n為奇，則插入右邊
故用個(gè)變量存儲(chǔ)插入的次數(shù)

代碼

運(yùn)行環(huán)境node v8.4

function Node(value) {
  this.value = value
  this.left = null
  this.right = null
}

function BinaryTree() {
  this.root = null // 樹(shù)根
  this.queue = [] // 存儲(chǔ)會(huì)被使用的父節(jié)點(diǎn)
  this.insertNum = 0 // 記錄插入操作的次數(shù)
}

BinaryTree.prototype.insert = function (value) {
  this.insertNum++ // 插入次數(shù)加1
    let node = new Node(value)
  if (!this.root) { // 判斷根節(jié)點(diǎn)是否存在
    this.root = node // 插入根節(jié)點(diǎn)
    this.queue.push(this.root) // 新節(jié)點(diǎn)入列
  } else { // 插入非根節(jié)點(diǎn)
    let parent = this.queue[0] // 被插入的父節(jié)點(diǎn)
    if (!(this.insertNum % 2)) { // 通過(guò)插入次數(shù)判斷左右
      parent.left = node // 插入左邊
      this.queue.push(parent.left) // 新節(jié)點(diǎn)入列
    } else {
      parent.right = node // 插入右邊
      this.queue.push(parent.right) // 新節(jié)點(diǎn)入列
      this.queue.shift() // 當(dāng)前父節(jié)點(diǎn)parent 已經(jīng)不可能再插入子節(jié)點(diǎn)，故出列
    }
  }
  return this
}

let binaryTree = new BinaryTree()
binaryTree.insert("A")
  .insert("B")
  .insert("C")
  .insert("D")
  .insert("E")
  .insert("F")

console.log(JSON.stringify(binaryTree.root, null, 4))

插入空節(jié)點(diǎn)

首先需要判斷插入的節(jié)點(diǎn)是否為空節(jié)點(diǎn)
若是空節(jié)點(diǎn)，其不會(huì)作為父節(jié)點(diǎn)被執(zhí)行插入操作，故不用入列

改進(jìn)代碼

BinaryTree.prototype.insert = function (value) {
  this.insertNum++ // 插入次數(shù)加1
    let node = (!value && typeof value === "object") ? null : new Node(value) // 判斷是否為空節(jié)點(diǎn)

  if (!this.root) { // 判斷根節(jié)點(diǎn)是否存在
    this.root = node // 插入根節(jié)點(diǎn)
    node && this.queue.push(this.root) // 非空節(jié)點(diǎn)入列
  } else { // 插入非根節(jié)點(diǎn)
    let parent = this.queue[0] // 被插入的父節(jié)點(diǎn)
    if (!(this.insertNum % 2)) { // 通過(guò)插入次數(shù)判斷左右
      parent.left = node // 插入左邊
      node && this.queue.push(parent.left) // 非空節(jié)點(diǎn)入列
    } else {
      parent.right = node // 插入右邊
      node && this.queue.push(parent.right) // 非空節(jié)點(diǎn)入列
      this.queue.shift() // 當(dāng)前父節(jié)點(diǎn)parent 已經(jīng)不可能再插入子節(jié)點(diǎn)，故出列
    }
  }
  return this
}

let binaryTree = new BinaryTree()
binaryTree.insert("A")
  .insert("B")
  .insert("C")
  .insert("D")
  .insert("E")
  .insert(null)
  .insert("F")
  .insert("G")

console.log(JSON.stringify(binaryTree.root, null, 4))