您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“javascript多叉樹經(jīng)典操作的方法”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“javascript多叉樹經(jīng)典操作的方法”吧!
多叉樹可以實現(xiàn)復雜的數(shù)據(jù)結(jié)構的存儲,通過遍歷方法可以方便高效的查找數(shù)據(jù),提高查找的效率,同時方便管理節(jié)點數(shù)據(jù)。javascript的DOM其實就是以多叉樹的形式存儲的。下面用javascript來實現(xiàn)多叉樹的數(shù)據(jù)結(jié)構
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測試運行效果如下:
到此,相信大家對“javascript多叉樹經(jīng)典操作的方法”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關內(nèi)容可以進入相關頻道進行查詢,關注我們,繼續(xù)學習!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。