摘要:像剛才的這幅圖,就是二叉搜索樹(shù)。而我們本文要學(xué)習(xí)的內(nèi)容,就是如何寫(xiě)一個(gè)二叉搜索樹(shù)。但在二叉搜索樹(shù)中,我們把節(jié)點(diǎn)成為鍵,這是術(shù)語(yǔ)。前端路漫漫,且行且歌的前端樂(lè)園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法四二叉搜索樹(shù)
我與二叉樹(shù)的前塵往事本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(一),棧與隊(duì)列
第二篇文章:學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(二):鏈表
第三篇文章:學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(三):集合
第四篇文章:學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(四):二叉搜索樹(shù)
在剛學(xué)編程時(shí),就知道有一種數(shù)據(jù)結(jié)構(gòu)叫“樹(shù)”,樹(shù)中的翹楚是“二叉樹(shù)”,“紅黑樹(shù)”等。
據(jù)說(shuō)“樹(shù)”構(gòu)在編程界呼風(fēng)喚雨無(wú)所不能。讓無(wú)數(shù)程序員聞風(fēng)喪膽。甚至在面試時(shí),更是有“手寫(xiě)二叉樹(shù)”,“翻轉(zhuǎn)二叉樹(shù)”等題目坐鎮(zhèn)。
好吧,我承認(rèn)這些在當(dāng)時(shí)都把我嚇住了。
但是當(dāng)我顫抖著打開(kāi)《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》,開(kāi)始敲下關(guān)于“樹(shù)”的代碼時(shí),突然覺(jué)得,好像也沒(méi)有那么難呢。
于是心懷激動(dòng),一口氣敲完了書(shū)上的例子,中途也思考了很久,不斷的在紙上演算等。但總的來(lái)說(shuō),還是學(xué)的很開(kāi)心的。
之前學(xué)的棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu),都是順序數(shù)據(jù)結(jié)構(gòu)。而樹(shù),將會(huì)是我們學(xué)的第一種非順序數(shù)據(jù)結(jié)構(gòu)。
放在現(xiàn)實(shí)里呢,有個(gè)很生動(dòng)的例子,公司組織架構(gòu)圖。長(zhǎng)這樣:
而我們要學(xué)的樹(shù),長(zhǎng)這樣:
其中,樹(shù)中的每個(gè)元素,都叫做節(jié)點(diǎn)。從節(jié)點(diǎn)延伸而下的,叫子節(jié)點(diǎn)。
樹(shù)頂部的節(jié)點(diǎn)叫根節(jié)點(diǎn)。每棵樹(shù)只有一個(gè)根節(jié)點(diǎn)。(圖中15就是根節(jié)點(diǎn))
在節(jié)點(diǎn)中,有子節(jié)點(diǎn)的節(jié)點(diǎn)也稱(chēng)為內(nèi)部節(jié)點(diǎn),沒(méi)有的話則被稱(chēng)為外部節(jié)點(diǎn)或者葉節(jié)點(diǎn)。
同時(shí)在節(jié)點(diǎn)中是有祖先和后代關(guān)系的,比如節(jié)點(diǎn)9的祖先就有13,7,6,15四個(gè)。
深度: 節(jié)點(diǎn)的深度取決于其祖先的數(shù)量,節(jié)點(diǎn)9的深度就是4。
樹(shù)的高度,樹(shù)的高度體現(xiàn)為節(jié)點(diǎn)深度的最大值。
比如上圖,節(jié)點(diǎn)深度最大值為4,則樹(shù)的高度為4。
二叉樹(shù)的最大特點(diǎn)就在于,它的節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn):左側(cè)子節(jié)點(diǎn)和右側(cè)子節(jié)點(diǎn)。
二叉搜索樹(shù)則是二叉樹(shù)的一種,但它只允許你在左側(cè)節(jié)點(diǎn)儲(chǔ)存比父節(jié)點(diǎn)小的值,右側(cè)只允許儲(chǔ)存比父節(jié)點(diǎn)大的值。
像剛才的這幅圖,就是二叉搜索樹(shù)。
而我們本文要學(xué)習(xí)的內(nèi)容,就是如何寫(xiě)一個(gè)二叉搜索樹(shù)。
JavaScipt中二叉搜索樹(shù)的實(shí)現(xiàn)首先,創(chuàng)建一個(gè)構(gòu)造函數(shù)。
/** * 二叉搜索樹(shù)的構(gòu)造函數(shù) */ function BinarySearchTree() { /** * 二叉搜索樹(shù)鍵的構(gòu)造函數(shù) * @param {Number} key 要生成的鍵值 */ var Node = function(key) { // 鍵值 this.key = key; // 左子節(jié)點(diǎn) this.left = null; // 右子節(jié)點(diǎn) this.right = null; } /** * 二叉樹(shù)的根節(jié)點(diǎn),不存在時(shí)表示為Null * @type {Null or Number} */ var root = null; }
在之前提到過(guò)的雙向鏈表中,每個(gè)節(jié)點(diǎn)包含兩個(gè)指針,一個(gè)指向左側(cè)節(jié)點(diǎn),一個(gè)指向右側(cè)節(jié)點(diǎn)。在二叉搜索樹(shù)中,每個(gè)節(jié)點(diǎn)也有兩個(gè)指針,一個(gè)指向左側(cè)子節(jié)點(diǎn),一個(gè)指向右側(cè)子節(jié)點(diǎn)。但在二叉搜索樹(shù)中,我們把節(jié)點(diǎn)成為鍵,這是術(shù)語(yǔ)。
二叉搜索樹(shù)需要有如下的方法:
insert(key): 向樹(shù)中插入一個(gè)新的鍵
inOrderTraverse(): 通過(guò)中序遍歷方式,遍歷所有節(jié)點(diǎn)
preOrderTranverse(): 通過(guò)先序遍歷方式,遍歷所有節(jié)點(diǎn)
postOrderTranverse(): 通過(guò)后序遍歷方式,遍歷所有節(jié)點(diǎn)
min(): 返回樹(shù)中最小的值
max(): 返回樹(shù)中最大的值
search(key): 搜索某個(gè)值,在樹(shù)中則返回true
remove(key): 從樹(shù)中移除某個(gè)鍵
二叉搜索樹(shù)的實(shí)現(xiàn),基本都與遞歸有關(guān)(對(duì)我來(lái)說(shuō)遞歸很繞,花了很久才理解)。如果不清楚遞歸相關(guān)概念,可以看看下面的參考鏈接。
insert方法:什么是遞歸
說(shuō)明:向樹(shù)中插入一個(gè)新的鍵
實(shí)現(xiàn):
/** * 插入某個(gè)鍵到二叉樹(shù)中 * @param {Number} key 要插入的鍵值 */ this.insert = function(key) { // 用傳入的值生成二叉樹(shù)的鍵 var newNode = new Node(key); // 根節(jié)點(diǎn)為Null時(shí),傳入的鍵則為根節(jié)點(diǎn) // 否則調(diào)用insertNode函數(shù)來(lái)插入子節(jié)點(diǎn) if (root === null) { root = newNode; } else { insertNode(root, newNode) } }; /** * 用于插入子節(jié)點(diǎn)。 * @param {Node} node 根節(jié)點(diǎn) * @param {Node} newNode 要插入的節(jié)點(diǎn) */ var insertNode = function(node, newNode) { //由于二叉搜索樹(shù)的性質(zhì),所以當(dāng)鍵值小于當(dāng)前所在節(jié)點(diǎn)的鍵值 //則使得左子結(jié)點(diǎn)成為新的要比較的節(jié)點(diǎn),進(jìn)行遞歸調(diào)用 //如果左子結(jié)點(diǎn)為null,則將鍵值賦值給左子結(jié)點(diǎn)。 //如果鍵值大于當(dāng)前所在節(jié)點(diǎn)的鍵值,原理同上。 if (newNode.key < node.key) { if (node.left === null) { node.left = newNode; } else { insertNode(node.left, newNode) } } else { if (node.right === null) { node.right = newNode } else { insertNode(node.right, newNode) } } };inOrderTraverse方法:
說(shuō)明:通過(guò)中序遍歷方式,遍歷所有節(jié)點(diǎn)
實(shí)現(xiàn):
/** * 中序遍歷操作,常用于排序。會(huì)把樹(shù)中元素從小到大的打印出來(lái)。 * 因?yàn)樵趈avascript的遞歸中,遇到遞歸是,會(huì)優(yōu)先調(diào)用遞歸的函數(shù)。直到遞歸不再進(jìn)行。 * 然后會(huì)在遞歸調(diào)用的最后一個(gè)函數(shù)中執(zhí)行其它語(yǔ)句。再一層層的升上去。 * 所以中序遍歷會(huì)有從小到大的輸出結(jié)果。 * 后續(xù)的先序和后續(xù)遍歷和這個(gè)原理差不多,取決于callback放在哪兒。 * * @param {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù) */ this.inOrderTraverse = function(callback) { inOrderTraverseNode(root, callback); }; /** * 中序遍歷的輔助函數(shù),用于遍歷節(jié)點(diǎn) * @param {Node} node 遍歷開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @param {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù) * @return {[type]} [description] */ var inOrderTraverseNode = function(node, callback) { // 當(dāng)前節(jié)點(diǎn)不為NULL則繼續(xù)遞歸調(diào)用 if (node != null) { inOrderTraverseNode(node.left, callback); // 獲取到節(jié)點(diǎn)后,調(diào)用的函數(shù) callback(node.key); inOrderTraverseNode(node.right, callback); } };
假如我們這兒加入打印節(jié)點(diǎn)值的函數(shù):
var printNode = function(value) { console.log(value); }; inOrderTraverse(printNode) // 輸出排序后樹(shù)的值preOrderTranverse方法:
說(shuō)明:通過(guò)先序遍歷方式,遍歷所有節(jié)點(diǎn)
實(shí)現(xiàn):
/** * 前序遍歷操作,常用于打印一個(gè)結(jié)構(gòu)化的文檔 * @param {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù) */ this.preOrderTranverse = function(callback) { preOrderTranverseNode(root, callback); }; /** * 前序遍歷的輔助函數(shù),用于遍歷節(jié)點(diǎn) * @param {Node} node 遍歷開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @param {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù) */ var preOrderTranverseNode = function(node, callback) { if (node != null) { callback(node.key); preOrderTranverseNode(node.left, callback); preOrderTranverseNode(node.right, callback); } };postOrderTranverse方法:
說(shuō)明:通過(guò)后序遍歷方式,遍歷所有節(jié)點(diǎn)
實(shí)現(xiàn):
/** * 后序遍歷操作,常用于計(jì)算所占空間 * @param {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù) */ this.postOrderTranverse = function(callback) { postOrderTranverseNode(root, callback); }; /** * 后序遍歷的輔助函數(shù),用于遍歷節(jié)點(diǎn) * @param {Node} node 遍歷開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @param {Function} callback 獲取到節(jié)點(diǎn)后的回調(diào)函數(shù) */ var postOrderTranverseNode = function(node, callback) { postOrderTranverseNode(node.left, callback); postOrderTranverseNode(node.right, callback); callback(node.key); };min方法:
說(shuō)明:返回樹(shù)中最小的值,由二叉搜索樹(shù)的性質(zhì)易知,最左側(cè)的為最小值。則只需取得最左側(cè)的值即可。
實(shí)現(xiàn):
/** * 返回樹(shù)中最小的值 * @return {Function} min函數(shù)的輔助函數(shù) */ this.min = function() { return minNode(root); }; /** * min函數(shù)的輔助函數(shù) * @param {Node} node 查找開(kāi)始的節(jié)點(diǎn),默認(rèn)為root */ var minNode = function(node) { // 如果node存在,則開(kāi)始搜索。能避免樹(shù)的根節(jié)點(diǎn)為Null的情況 if (node) { // 只要樹(shù)的左側(cè)子節(jié)點(diǎn)不為null,則把左子節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)。 // 若左子節(jié)點(diǎn)為null,則該節(jié)點(diǎn)肯定為最小值。 while (node && node.left !== null) { node = node.left; } return node.key; } return null; };max方法:
說(shuō)明:返回樹(shù)中最大的值,由min函數(shù)易知,最大值在最右側(cè)。
實(shí)現(xiàn):
/** * 返回樹(shù)中最大的值 * @return {Function} max函數(shù)的輔助函數(shù) */ this.max = function() { return maxNode(root); }; /** * max函數(shù)的輔助函數(shù) * @param {Node} node 查找開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @return {Key} 節(jié)點(diǎn)的值 */ var maxNode = function(node) { if (node) { while (node && node.right !== null) { node = node.right; } return node.key; } return null; };search方法:
說(shuō)明: 搜索某個(gè)值,在樹(shù)中則返回true
實(shí)現(xiàn):
/** * 搜索某個(gè)值是否存在于樹(shù)中 * @param {Node} key 搜索開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @return {Function} search函數(shù)的輔助函數(shù) */ this.search = function(key) { return searchNode(root, key); }; /** * search函數(shù)的輔助函數(shù) * @param {Node} node 搜索開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @param {Key} key 要搜索的鍵值 * @return {Boolean} 找到節(jié)點(diǎn)則返回true,否則返回false */ var searchNode = function(node, key) { // 如果根節(jié)點(diǎn)不存在,則直接返回null if (node === null) { return false; } else if (key < node.key) { searchNode(node.left, key) } else if (key > node.key) { searchNode(node.right, key) } else { // 如果該節(jié)點(diǎn)值等于傳入的值,返回true return true; } };remove方法:
說(shuō)明:從樹(shù)中移除某個(gè)鍵,要應(yīng)對(duì)的場(chǎng)景:
只是一個(gè)葉節(jié)點(diǎn)
有一個(gè)子節(jié)點(diǎn)
有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
因?yàn)橐獞?yīng)付不同的場(chǎng)景,所以這是最麻煩的方法了。讓我思考了好久才理解。如果你覺(jué)得看不懂的話,可以下載源代碼把這一段寫(xiě)一遍。
實(shí)現(xiàn):
/** * 從樹(shù)中移除某個(gè)鍵 * @param {Key} key 要移除的鍵值 * @return {Function} remove函數(shù)的輔助函數(shù) */ this.remove = function(key) { root = removeNode(root, key); }; /** * remove函數(shù)的輔助函數(shù) * @param {Node} node 搜索開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @param {Key} key 要移除的鍵值 * @return {Boolean} 移除成功則返回true,否則返回false */ var removeNode = function(node, key) { // 如果根節(jié)點(diǎn)不存在,則直接返回null if (node === root) { return null; } // 未找到節(jié)點(diǎn)前,繼續(xù)遞歸調(diào)用。 if (key < node.key) { node.left = removeNode(node.left, key) return node; } else if (key > node.key) { node.right = removeNode(node.right, key) return node; } else { // 第一種場(chǎng)景:只是一個(gè)葉節(jié)點(diǎn) // 這種情況只需要直接把節(jié)點(diǎn)賦值為null即可 if (node.left === null && node.right === null) { node = null; // 處理完直接return節(jié)點(diǎn) return node; } // 第二種場(chǎng)景:有一個(gè)子節(jié)點(diǎn) // 如果左節(jié)點(diǎn)為null,則代表右節(jié)點(diǎn)存在。 // 于是把當(dāng)前節(jié)點(diǎn)賦值為存在的那個(gè)子節(jié)點(diǎn) if (node.left === null) { node = node.right; // 處理完直接return節(jié)點(diǎn) return node; } else if (node.right == null) { node = node.left; // 處理完直接return節(jié)點(diǎn) return node; } // 第三種場(chǎng)景:有兩個(gè)子節(jié)點(diǎn) // 首先加入輔助節(jié)點(diǎn),同時(shí)找尋右子節(jié)點(diǎn)中的最小節(jié)點(diǎn) // 并把當(dāng)前節(jié)點(diǎn)替換為右子節(jié)點(diǎn)中的最小節(jié)點(diǎn) // 同時(shí)為了避免節(jié)點(diǎn)重復(fù),移除右子節(jié)點(diǎn)中的最小節(jié)點(diǎn) var aux = findMinNode(node.right); node.key = aux.key; node.right = removeNode(node.right, aux.key); // 處理完直接return節(jié)點(diǎn) return node; } }; /** * remove函數(shù)的輔助函數(shù) * @param {Node} node 查找開(kāi)始的節(jié)點(diǎn),默認(rèn)為root * @return {Node} 最小的節(jié)點(diǎn) */ var findMinNode = function(node) { // 如果node存在,則開(kāi)始搜索。能避免樹(shù)的根節(jié)點(diǎn)為Null的情況 if (node) { // 只要樹(shù)的左側(cè)子節(jié)點(diǎn)不為null,則把左子節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)。 // 若左子節(jié)點(diǎn)為null,則該節(jié)點(diǎn)肯定為最小值。 while (node && node.left !== null) { node = node.left; } return node; } return null; };源代碼:
源代碼在此~
感想二叉搜索樹(shù)-源代碼
寫(xiě)文章的時(shí)候,人有點(diǎn)感冒,暈暈乎乎的。不過(guò)寫(xiě)完之后就好多了,腦子清醒了許多。
二叉樹(shù)這一章,就我而言感慨萬(wàn)分,也算是暫時(shí)滿足了自己對(duì)數(shù)據(jù)結(jié)構(gòu)中“樹(shù)”的向往與愿望,也不是之前看數(shù)據(jù)結(jié)構(gòu)中那種迷茫的感覺(jué)。
能用JavaScript親手實(shí)現(xiàn),還是非常開(kāi)心的。
前端路漫漫,且行且歌~
Lxxyx的前端樂(lè)園
原文鏈接:寒假前端學(xué)習(xí)(6)——學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(四):二叉搜索樹(shù)
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://www.ezyhdfw.cn/yun/78524.html
摘要:原文博客地址學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)四樹(shù)知乎專(zhuān)欄簡(jiǎn)書(shū)專(zhuān)題前端進(jìn)擊者知乎前端進(jìn)擊者簡(jiǎn)書(shū)博主博客地址的個(gè)人博客人之所能,不能兼?zhèn)洌瑮壠渌?,取其所長(zhǎng)。通常子樹(shù)被稱(chēng)作左子樹(shù)和右子樹(shù)。敬請(qǐng)期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)五圖參考文章樹(shù)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù) 前言 總括: 本文講解了數(shù)據(jù)結(jié)構(gòu)中的[樹(shù)]的概念,盡可能通俗易懂的解釋樹(shù)這種數(shù)據(jù)結(jié)構(gòu)的概念,使用javascript實(shí)現(xiàn)了樹(shù),如有紕漏,歡迎批評(píng)指正。 ...
摘要:二叉搜索樹(shù)是二叉樹(shù)的一種,其特征是左側(cè)子節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值,右側(cè)子節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大或等于父節(jié)點(diǎn)的值。實(shí)現(xiàn)和這個(gè)兩個(gè)方法其實(shí)挺簡(jiǎn)單的,最小的節(jié)點(diǎn)就在二叉搜索樹(shù)的最左反之,最大的就在最右。 本系列所有文章:第一篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)...
摘要:筆者作為一位,將工作以來(lái)用到的各種優(yōu)秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤(pán),此前端知識(shí)點(diǎn)大百科全書(shū)前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計(jì)算數(shù)組的極值技巧使你的更加專(zhuān)業(yè)前端掘金一個(gè)幫你提升技巧的收藏集。 CSS 樣式畫(huà)各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經(jīng)常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會(huì)用到。會(huì)持續(xù)更新… 一、...
摘要:筆者作為一位,將工作以來(lái)用到的各種優(yōu)秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤(pán),此前端知識(shí)點(diǎn)大百科全書(shū)前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計(jì)算數(shù)組的極值技巧使你的更加專(zhuān)業(yè)前端掘金一個(gè)幫你提升技巧的收藏集。 CSS 樣式畫(huà)各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經(jīng)常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會(huì)用到。會(huì)持續(xù)更新… 一、...
閱讀 3189·2021-11-24 09:38
閱讀 1416·2021-09-22 15:27
閱讀 3046·2021-09-10 10:51
閱讀 1589·2021-09-09 09:33
閱讀 992·2021-08-09 13:47
閱讀 2166·2019-08-30 13:05
閱讀 957·2019-08-29 15:15
閱讀 2624·2019-08-29 12:21