這篇文章給大家分享的是有關(guān)javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹經(jīng)典操作的示例分析的內(nèi)容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
成都創(chuàng)新互聯(lián)公司主要業(yè)務(wù)有網(wǎng)站營銷策劃、網(wǎng)站設(shè)計制作、網(wǎng)站制作、微信公眾號開發(fā)、小程序開發(fā)、HTML5建站、程序開發(fā)等業(yè)務(wù)。一次合作終身朋友,是我們奉行的宗旨;我們不僅僅把客戶當客戶,還把客戶視為我們的合作伙伴,在開展業(yè)務(wù)的過程中,公司還積累了豐富的行業(yè)經(jīng)驗、全網(wǎng)營銷推廣資源和合作伙伴關(guān)系資源,并逐漸建立起規(guī)范的客戶服務(wù)和保障體系。多叉樹可以實現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的存儲,通過遍歷方法可以方便高效的查找數(shù)據(jù),提高查找的效率,同時方便管理節(jié)點數(shù)據(jù)。javascript的DOM其實就是以多叉樹的形式存儲的。下面用javascript來實現(xiàn)多叉樹的數(shù)據(jù)結(jié)構(gòu)
1、創(chuàng)造一個節(jié)點
數(shù)據(jù)是以節(jié)點的形式存儲的:
class Node { constructor(data) { this.data = data; this.parent = null; this.children = []; } }
2、創(chuàng)造樹
樹用來連接節(jié)點,就像真實世界樹的主干一樣,延伸著很多分支
class MultiwayTree { constructor() { this._root = null; } }
3、添加一個節(jié)點
function add(data, toData, traversal) { let node = new Node(data) // 第一次添加到根節(jié)點 // 返回值為this,便于鏈式添加節(jié)點 if (this._root === null) { this._root = node; return this; } let parent = null, callback = function(node) { if (node.data === toData) { parent = node; return true; } }; // 根據(jù)遍歷方法查找父節(jié)點(遍歷方法后面會講到),然后把節(jié)點添加到父節(jié)點 // 的children數(shù)組里 // 查找方法contains后面會講到 this.contains(callback, traversal); if (parent) { parent.children.push(node); node.parent = parent; return this; } else { throw new Error('Cannot add node to a non-existent parent.'); } }
4、深度優(yōu)先遍歷
深度優(yōu)先會盡量先從子節(jié)點查找,子節(jié)點查找完再從兄弟節(jié)點查找,適合數(shù)據(jù)深度比較大的情況,如文件目錄
function traverseDF(callback) { let stack = [], found = false; stack.unshift(this._root); let currentNode = stack.shift(); while(!found && currentNode) { // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個后繼續(xù)查找 found = callback(currentNode) === true ? true : false; if (!found) { // 每次把子節(jié)點置于堆棧最前頭,下次查找就會先查找子節(jié)點 stack.unshift(...currentNode.children); currentNode = stack.shift(); } } }
5、廣度優(yōu)先遍歷
廣度優(yōu)先遍歷會優(yōu)先查找兄弟節(jié)點,一層層往下找,適合子項較多情況,如公司崗位級別
function traverseBF(callback) { let queue = [], found = false; queue.push(this._root); let currentNode = queue.shift(); while(!found && currentNode) { // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個后繼續(xù)查找 found = callback(currentNode) === true ? true : false; if (!found) { // 每次把子節(jié)點置于隊列最后,下次查找就會先查找兄弟節(jié)點 queue.push(...currentNode.children) currentNode = queue.shift(); } } }
6、包含節(jié)點
function contains(callback, traversal) { traversal.call(this, callback); }
回調(diào)函數(shù)算法可自己根據(jù)情況實現(xiàn),靈活度較高
7、移除節(jié)點
// 返回被移除的節(jié)點 function remove(data, fromData, traversal) { let parent = null, childToRemove = null, callback = function(node) { if (node.data === fromData) { parent = node; return true; } }; this.contains(callback, traversal); if (parent) { let index = this._findIndex(parent.children, data); if (index < 0) { throw new Error('Node to remove does not exist.'); } else { childToRemove = parent.children.splice(index, 1); } } else { throw new Error('Parent does not exist.'); } return childToRemove; }
_findIndex實現(xiàn):
function _findIndex(arr, data) { let index = -1; for (let i = 0, len = arr.length; i < len; i++) { if (arr[i].data === data) { index = i; break; } } return index; }
完整算法
class Node { constructor(data) { this.data = data; this.parent = null; this.children = []; } } class MultiwayTree { constructor() { this._root = null; } //深度優(yōu)先遍歷 traverseDF(callback) { let stack = [], found = false; stack.unshift(this._root); let currentNode = stack.shift(); while(!found && currentNode) { found = callback(currentNode) === true ? true : false; if (!found) { stack.unshift(...currentNode.children); currentNode = stack.shift(); } } } //廣度優(yōu)先遍歷 traverseBF(callback) { let queue = [], found = false; queue.push(this._root); let currentNode = queue.shift(); while(!found && currentNode) { found = callback(currentNode) === true ? true : false; if (!found) { queue.push(...currentNode.children) currentNode = queue.shift(); } } } contains(callback, traversal) { traversal.call(this, callback); } add(data, toData, traversal) { let node = new Node(data) if (this._root === null) { this._root = node; return this; } let parent = null, callback = function(node) { if (node.data === toData) { parent = node; return true; } }; this.contains(callback, traversal); if (parent) { parent.children.push(node); node.parent = parent; return this; } else { throw new Error('Cannot add node to a non-existent parent.'); } } remove(data, fromData, traversal) { let parent = null, childToRemove = null, callback = function(node) { if (node.data === fromData) { parent = node; return true; } }; this.contains(callback, traversal); if (parent) { let index = this._findIndex(parent.children, data); if (index < 0) { throw new Error('Node to remove does not exist.'); } else { childToRemove = parent.children.splice(index, 1); } } else { throw new Error('Parent does not exist.'); } return childToRemove; } _findIndex(arr, data) { let index = -1; for (let i = 0, len = arr.length; i < len; i++) { if (arr[i].data === data) { index = i; break; } } return index; } }
控制臺測試代碼
var tree = new MultiwayTree(); tree.add('a') .add('b', 'a', tree.traverseBF) .add('c', 'a', tree.traverseBF) .add('d', 'a', tree.traverseBF) .add('e', 'b', tree.traverseBF) .add('f', 'b', tree.traverseBF) .add('g', 'c', tree.traverseBF) .add('h', 'c', tree.traverseBF) .add('i', 'd', tree.traverseBF); console.group('traverseDF'); tree.traverseDF(function(node) { console.log(node.data); }); console.groupEnd('traverseDF'); console.group('traverseBF'); tree.traverseBF(function(node) { console.log(node.data); }); console.groupEnd('traverseBF'); // 深度優(yōu)先查找 console.group('contains1'); tree.contains(function(node) { console.log(node.data); if (node.data === 'f') { return true; } }, tree.traverseDF); console.groupEnd('contains1') // 廣度優(yōu)先查找 console.group('contains2'); tree.contains(function(node) { console.log(node.data); if (node.data === 'f') { return true; } }, tree.traverseBF); console.groupEnd('contains2'); tree.remove('g', 'c', tree.traverseBF);
這里使用在線HTML/CSS/JavaScript代碼運行工具:http://tools.jb51.net/code/HtmlJsRun測試運行效果如下:
感謝各位的閱讀!關(guān)于“javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹經(jīng)典操作的示例分析”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
當前標題:javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹經(jīng)典操作的示例分析-創(chuàng)新互聯(lián)
路徑分享:http://www.muchs.cn/article40/dpcieo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供電子商務(wù)、網(wǎng)站排名、網(wǎng)站改版、App設(shè)計、微信公眾號、網(wǎng)站內(nèi)鏈
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容