資訊專欄INFORMATION COLUMN
摘要：每次插入的新節(jié)點都會入列。同時，若新節(jié)點被插入到父節(jié)點的右下方，則該父節(jié)點出列。
模擬過程
插入根節(jié)點A
在父節(jié)點A的左下方插入子節(jié)點B
在父節(jié)點A的右下方插入子節(jié)點C
在父節(jié)點B的左下方插入子節(jié)點D
在父節(jié)點B的右下方插入子節(jié)點E
在父節(jié)點C的左下方插入子節(jié)點F
...
每次插入節(jié)點需明確被插入的父節(jié)點以及被插入的位置（左右）
第1步中，需將A存儲，因為A在第2，3步中被取出，作為插入操作的父節(jié)點
第2步中，需將B存儲，因為B在第4，5步中被取出，作為插入操作的父節(jié)點
第3步中，需將C存儲，因為C在第6步中被取出，作為插入操作的父節(jié)點，與此同時，A在被執(zhí)行右下方的插入操作后，A不能再被插入子節(jié)點
...
第5步中，需將E存儲，其在后續(xù)的操作中會被取出，作為插入操作的父節(jié)點，與此同時，B與A一樣，在被執(zhí)行右下方的插入操作后，B不能再被插入子節(jié)點
故建個隊列，將后續(xù)操作中會被取出的節(jié)點存儲，不會再被取出的節(jié)點移除。每次插入的新節(jié)點都會入列。同時，若新節(jié)點被插入到父節(jié)點的右下方，則該父節(jié)點出列。
被插入的位置可以通過插入的次數(shù)來判斷，若是第1次插入，則是根節(jié)點，若是第n(n>1)次插入，n為偶，則插入左邊，n為奇，則插入右邊
故用個變量存儲插入的次數(shù)
運行環(huán)境node v8.4
function Node(value) {
this.value = value
this.left = null
this.right = null
}
function BinaryTree() {
this.root = null // 樹根
this.queue = [] // 存儲會被使用的父節(jié)點
this.insertNum = 0 // 記錄插入操作的次數(shù)
}
BinaryTree.prototype.insert = function (value) {
this.insertNum++ // 插入次數(shù)加1
let node = new Node(value)
if (!this.root) { // 判斷根節(jié)點是否存在
this.root = node // 插入根節(jié)點
this.queue.push(this.root) // 新節(jié)點入列
} else { // 插入非根節(jié)點
let parent = this.queue[0] // 被插入的父節(jié)點
if (!(this.insertNum % 2)) { // 通過插入次數(shù)判斷左右
parent.left = node // 插入左邊
this.queue.push(parent.left) // 新節(jié)點入列
} else {
parent.right = node // 插入右邊
this.queue.push(parent.right) // 新節(jié)點入列
this.queue.shift() // 當前父節(jié)點parent 已經(jīng)不可能再插入子節(jié)點，故出列
}
}
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é)點
首先需要判斷插入的節(jié)點是否為空節(jié)點
若是空節(jié)點，其不會作為父節(jié)點被執(zhí)行插入操作，故不用入列
BinaryTree.prototype.insert = function (value) {
this.insertNum++ // 插入次數(shù)加1
let node = (!value && typeof value === "object") ? null : new Node(value) // 判斷是否為空節(jié)點
if (!this.root) { // 判斷根節(jié)點是否存在
this.root = node // 插入根節(jié)點
node && this.queue.push(this.root) // 非空節(jié)點入列
} else { // 插入非根節(jié)點
let parent = this.queue[0] // 被插入的父節(jié)點
if (!(this.insertNum % 2)) { // 通過插入次數(shù)判斷左右
parent.left = node // 插入左邊
node && this.queue.push(parent.left) // 非空節(jié)點入列
} else {
parent.right = node // 插入右邊
node && this.queue.push(parent.right) // 非空節(jié)點入列
this.queue.shift() // 當前父節(jié)點parent 已經(jīng)不可能再插入子節(jié)點，故出列
}
}
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))
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/89168.html
摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現(xiàn)求二叉樹的子樹求節(jié)點的父節(jié)點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據(jù)根節(jié)點的遍歷次序分為先根遍歷中根遍歷后根遍歷。 聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...
摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...
摘要：數(shù)據(jù)結(jié)構(gòu)程序數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的關系的數(shù)據(jù)元素集合的表示。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結(jié)點。 本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數(shù)據(jù)結(jié)構(gòu)和查找算法 本文主要是基礎的數(shù)據(jù)結(jié)構(gòu)和算法概念，可能部分地方會涉及更高級的算法和算法，具體內(nèi)容以...
閱讀 3676·2021-09-24 09:48
閱讀 1179·2021-09-10 10:51
閱讀 3361·2019-08-30 13:03
閱讀 3400·2019-08-30 12:51
閱讀 1449·2019-08-30 11:22
閱讀 1160·2019-08-29 18:38
閱讀 2121·2019-08-29 16:41
閱讀 3335·2019-08-29 15:32
