二叉樹的順序插入

forsigner 發布于2019-08-21 17:08 / 1039人閱讀

摘要：每次插入的新節點都會入列。同時，若新節點被插入到父節點的右下方，則該父節點出列。

模擬過程

插入根節點A

在父節點A的左下方插入子節點B

在父節點A的右下方插入子節點C

在父節點B的左下方插入子節點D

在父節點B的右下方插入子節點E

在父節點C的左下方插入子節點F
...

分析過程

每次插入節點需明確被插入的父節點以及被插入的位置（左右）

明確被插入的父節點

第1步中，需將A存儲，因為A在第2，3步中被取出，作為插入操作的父節點
第2步中，需將B存儲，因為B在第4，5步中被取出，作為插入操作的父節點
第3步中，需將C存儲，因為C在第6步中被取出，作為插入操作的父節點，與此同時，A在被執行右下方的插入操作后，A不能再被插入子節點
...
第5步中，需將E存儲，其在后續的操作中會被取出，作為插入操作的父節點，與此同時，B與A一樣，在被執行右下方的插入操作后，B不能再被插入子節點
故建個隊列，將后續操作中會被取出的節點存儲，不會再被取出的節點移除。每次插入的新節點都會入列。同時，若新節點被插入到父節點的右下方，則該父節點出列。

明確被插入的位置

被插入的位置可以通過插入的次數來判斷，若是第1次插入，則是根節點，若是第n(n>1)次插入，n為偶，則插入左邊，n為奇，則插入右邊
故用個變量存儲插入的次數

代碼

運行環境node v8.4

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

function BinaryTree() {
  this.root = null // 樹根
  this.queue = [] // 存儲會被使用的父節點
  this.insertNum = 0 // 記錄插入操作的次數
}

BinaryTree.prototype.insert = function (value) {
  this.insertNum++ // 插入次數加1
    let node = new Node(value)
  if (!this.root) { // 判斷根節點是否存在
    this.root = node // 插入根節點
    this.queue.push(this.root) // 新節點入列
  } else { // 插入非根節點
    let parent = this.queue[0] // 被插入的父節點
    if (!(this.insertNum % 2)) { // 通過插入次數判斷左右
      parent.left = node // 插入左邊
      this.queue.push(parent.left) // 新節點入列
    } else {
      parent.right = node // 插入右邊
      this.queue.push(parent.right) // 新節點入列
      this.queue.shift() // 當前父節點parent 已經不可能再插入子節點，故出列
    }
  }
  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))

插入空節點

首先需要判斷插入的節點是否為空節點
若是空節點，其不會作為父節點被執行插入操作，故不用入列

改進代碼

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

  if (!this.root) { // 判斷根節點是否存在
    this.root = node // 插入根節點
    node && this.queue.push(this.root) // 非空節點入列
  } else { // 插入非根節點
    let parent = this.queue[0] // 被插入的父節點
    if (!(this.insertNum % 2)) { // 通過插入次數判斷左右
      parent.left = node // 插入左邊
      node && this.queue.push(parent.left) // 非空節點入列
    } else {
      parent.right = node // 插入右邊
      node && this.queue.push(parent.right) // 非空節點入列
      this.queue.shift() // 當前父節點parent 已經不可能再插入子節點，故出列
    }
  }
  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))

云服務器 GPU云服務器二叉樹的遍歷二叉樹的存儲二叉樹的存儲結構 java二叉樹的構建

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

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

Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)

摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...

muddyway 2019-08-16 11:15 評論0 收藏0
數據結構與算法:二叉樹算法

摘要：因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題內容銜接上一章數據結構與算法:常見排序算法內容提要什么是樹　　- 為什么使用樹二叉樹二叉查找樹紅黑樹Ｂ、Ｂ＋樹堆伸展樹樹可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

Little_XM 2019-08-22 11:09 評論0 收藏0
樹及其外部存儲

摘要：切記，紅黑樹在旋轉和顏色變換的過程中，必須遵守紅黑樹的幾條規則。樹的外部存儲磁盤布局計算機中的機械磁盤是由磁頭和圓盤組成，每個圓盤上劃分為多個磁道，每個磁道又劃分為多個扇區。術語 showImg(https://segmentfault.com/img/bVbai3r?w=643&h=407); 根 ????樹最頂端的節點稱為根，一棵樹只有一個根父節點 ????每個節...

_Dreams 2019-08-15 15:58 評論0 收藏0
基礎數據結構和算法概念

摘要：數據結構程序數據結構算法數據結構基本概念數據的邏輯結構反映數據元素之間的關系的數據元素集合的表示。這兩部分信息組成數據元素的存儲映象，稱為結點。本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客基于 Javascript 的排序算法基于 javascript 的基本數據結構和查找算法本文主要是基礎的數據結構和算法概念，可能部分地方會涉及更高級的算法和算法，具體內容以...

fsmStudy 2019-08-23 11:52 評論0 收藏0