資訊專欄INFORMATION COLUMN
摘要：代碼實現(xiàn)創(chuàng)建一個排序二叉樹節(jié)點類根節(jié)點插入節(jié)點以上便是創(chuàng)建排序二叉樹的實現(xiàn)方式重點在于插入節(jié)點的具體實現(xiàn)，即注釋的代碼片段。
排序二叉樹
如上圖為典型的排序二叉樹，左孩子的值比節(jié)點的值小，右孩子的值比節(jié)點的值大，關(guān)于具體的樹的定義及二叉樹的定義可以百度或查閱相關(guān)資料。
排序二叉樹的創(chuàng)建創(chuàng)建原理
排序二叉樹的創(chuàng)建原理與排序二叉樹的定義一致，即左孩子的值比當(dāng)前節(jié)點的值小，右孩子的值比當(dāng)前節(jié)點的值大。
代碼實現(xiàn)
binary-tree
以上便是創(chuàng)建排序二叉樹的實現(xiàn)方式：
重點在于插入節(jié)點的具體實現(xiàn)，即注釋1的代碼片段。
其中比較難理解的點在于遞歸是如何執(zhí)行，
取當(dāng)前的節(jié)點為{key: 1, left:null, right:null},則當(dāng)前樹如下圖：
對該樹進(jìn)行插入
var insertNode = function(node, newNode) {
if(node !== null) {
if(newNode.key < node.key) {
insertNode(node.left, newNode)
if(node.left == null) {
node.left = newNode
}
}else{
insertNode(node.right, newNode)
if(node.right == null) {
node.right = newNode
}
}
}
return null
}
首先由根節(jié)點8出發(fā)，進(jìn)入node的key為8的棧內(nèi)1比根節(jié)點8要小，進(jìn)入遞歸，即進(jìn)入到了node的key為3的棧內(nèi)，如下所示：
3
-----------------
8
--------------------------
當(dāng)前的值比3小再進(jìn)入3的左孩子null的棧內(nèi)
null
------------
3
-----------------
8
--------------------------
由于null的棧內(nèi)，node為null，立即退出當(dāng)前棧，返回至node的key為3的棧，發(fā)現(xiàn)左孩子為null，則將key為1的node變成key為3的node的左孩子，同時退出3的棧，返回至8的棧，8的棧左孩子不null,不做任何操作，知道當(dāng)前方法執(zhí)行完畢，跳出8的棧，返回至方法所在的執(zhí)行環(huán)境的棧，節(jié)點插入完畢，再進(jìn)行下一個節(jié)點的插入，操作則同上。以上的解釋，如果配合上瀏覽器的斷點調(diào)試，食用更佳，更好理解程序的整個執(zhí)行過程。
當(dāng)所有節(jié)點插入完畢之后，該排序二叉樹也創(chuàng)建完畢。
二叉樹創(chuàng)建完畢之后則可對二叉樹進(jìn)行相關(guān)的操作（遍歷，查找，節(jié)點刪除等）【待續(xù)】
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/96893.html
摘要：桶排序與計數(shù)排序的區(qū)別桶排序中一個桶可以放一個范圍內(nèi)的多個數(shù)據(jù)，在各個桶中又可以用其他方法排序，其快速之處在于只用對比同一個桶內(nèi)的數(shù)字而無需與其他桶的數(shù)字作對比。與計數(shù)排序相比，桶排序需要作二次對比，但可省略桶的個數(shù)。 哈希表（Hash Table） 所有符合鍵值對即key-value的結(jié)構(gòu)就是哈希。數(shù)組其實也是一種哈希。 計數(shù)排序（復(fù)雜度(n+max)）無法統(tǒng)計負(fù)數(shù)和小數(shù)，需要一個...
摘要：使用實現(xiàn)排序二叉樹排序二叉樹的定義二叉樹的基礎(chǔ)上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。下期內(nèi)容實現(xiàn)排序二叉樹的中序前序后續(xù)遍歷實現(xiàn)二叉樹的節(jié)點查找功能實現(xiàn)排序二叉樹的刪除節(jié)點功能應(yīng)用排序二叉樹實現(xiàn)一個小游戲 使用javascript實現(xiàn)排序二叉樹（1） 排序二叉樹的定義： 二叉樹的基礎(chǔ)上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。 show...
摘要：二叉樹二叉樹是一種樹形結(jié)構(gòu)，它的特點是每個節(jié)點最多只有兩個分支節(jié)點，一棵二叉樹通常由根節(jié)點，分支節(jié)點，葉子節(jié)點組成。 二叉樹 二叉樹(Binary Tree)是一種樹形結(jié)構(gòu)，它的特點是每個節(jié)點最多只有兩個分支節(jié)點，一棵二叉樹通常由根節(jié)點，分支節(jié)點，葉子節(jié)點組成。而每個分支節(jié)點也常常被稱作為一棵子樹。 showImg(https://segmentfault.com/img/bVbmEd...
摘要：前言可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復(fù)制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈表數(shù)據(jù)結(jié)構(gòu)不清楚的最好先看一下本人之前寫的數(shù)據(jù)結(jié)構(gòu)鏈表二叉樹二叉樹是一種樹形結(jié)構(gòu)，它的特點是 前言 可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復(fù)制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈...
閱讀 2362·2021-09-27 13:35
閱讀 618·2019-08-30 15:55
閱讀 869·2019-08-30 15:53
閱讀 614·2019-08-30 15:52
閱讀 2209·2019-08-30 12:59
閱讀 2349·2019-08-29 16:42
閱讀 1551·2019-08-26 18:26
閱讀 2525·2019-08-26 13:48
