javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹(shù)經(jīng)典操作示例【創(chuàng)建、添加、遍歷、移除等】
本文實(shí)例講述了javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹(shù)經(jīng)典操作。分享給大家供大家參考,具體如下:
多叉樹(shù)可以實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ),通過(guò)遍歷方法可以方便高效的查找數(shù)據(jù),提高查找的效率,同時(shí)方便管理節(jié)點(diǎn)數(shù)據(jù)。javascript的DOM其實(shí)就是以多叉樹(shù)的形式存儲(chǔ)的。下面用javascript來(lái)實(shí)現(xiàn)多叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)
1、創(chuàng)造一個(gè)節(jié)點(diǎn)
數(shù)據(jù)是以節(jié)點(diǎn)的形式存儲(chǔ)的:
class Node { constructor(data) { this.data = data; this.parent = null; this.children = []; } }
2、創(chuàng)造樹(shù)
樹(shù)用來(lái)連接節(jié)點(diǎn),就像真實(shí)世界樹(shù)的主干一樣,延伸著很多分支
class MultiwayTree { constructor() { this._root = null; } }
3、添加一個(gè)節(jié)點(diǎn)
function add(data, toData, traversal) { let node = new Node(data) // 第一次添加到根節(jié)點(diǎn) // 返回值為this,便于鏈?zhǔn)教砑庸?jié)點(diǎn) 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é)點(diǎn)(遍歷方法后面會(huì)講到),然后把節(jié)點(diǎn)添加到父節(jié)點(diǎn) // 的children數(shù)組里 // 查找方法contains后面會(huì)講到 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)先會(huì)盡量先從子節(jié)點(diǎn)查找,子節(jié)點(diǎn)查找完再?gòu)男值芄?jié)點(diǎn)查找,適合數(shù)據(jù)深度比較大的情況,如文件目錄
function traverseDF(callback) { let stack = [], found = false; stack.unshift(this._root); let currentNode = stack.shift(); while(!found && currentNode) { // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個(gè)后繼續(xù)查找 found = callback(currentNode) === true ? true : false; if (!found) { // 每次把子節(jié)點(diǎn)置于堆棧最前頭,下次查找就會(huì)先查找子節(jié)點(diǎn) stack.unshift(...currentNode.children); currentNode = stack.shift(); } } }
5、廣度優(yōu)先遍歷
廣度優(yōu)先遍歷會(huì)優(yōu)先查找兄弟節(jié)點(diǎn),一層層往下找,適合子項(xiàng)較多情況,如公司崗位級(jí)別
function traverseBF(callback) { let queue = [], found = false; queue.push(this._root); let currentNode = queue.shift(); while(!found && currentNode) { // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個(gè)后繼續(xù)查找 found = callback(currentNode) === true ? true : false; if (!found) { // 每次把子節(jié)點(diǎn)置于隊(duì)列最后,下次查找就會(huì)先查找兄弟節(jié)點(diǎn) queue.push(...currentNode.children) currentNode = queue.shift(); } } }
6、包含節(jié)點(diǎn)
function contains(callback, traversal) { traversal.call(this, callback); }
回調(diào)函數(shù)算法可自己根據(jù)情況實(shí)現(xiàn),靈活度較高
7、移除節(jié)點(diǎn)
// 返回被移除的節(jié)點(diǎn) 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實(shí)現(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; } }
控制臺(tái)測(cè)試代碼
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代碼運(yùn)行工具:http://tools.jb51.net/code/HtmlJsRun測(cè)試運(yùn)行效果如下:
感興趣的朋友可以自己測(cè)試一下看看運(yùn)行效果。
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
- JavaScript 處理樹(shù)數(shù)據(jù)結(jié)構(gòu)的方法示例
- ReactJs實(shí)現(xiàn)樹(shù)形結(jié)構(gòu)的數(shù)據(jù)顯示的組件的示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實(shí)現(xiàn)
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之集合(Set)
- 通過(guò)Jquery遍歷Json的兩種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)代碼
- js圖數(shù)據(jù)結(jié)構(gòu)處理 迪杰斯特拉算法代碼實(shí)例
相關(guān)文章
小程序安全指南之如何禁止外部直接跳轉(zhuǎn)到小程序某頁(yè)面
由于小程序跳轉(zhuǎn)的對(duì)象比較多,各自的規(guī)則又不一樣,因此小程序跳轉(zhuǎn)外部鏈接是用戶咨詢較多的問(wèn)題之一,下面這篇文章主要給大家介紹了關(guān)于小程序安全指南之如何禁止外部直接跳轉(zhuǎn)到小程序某頁(yè)面的相關(guān)資料,需要的朋友可以參考下2022-09-09TypeScript基礎(chǔ)入門(mén)教程之三重斜線指令詳解
這篇文章主要給大家介紹了關(guān)于TypeScript基礎(chǔ)入門(mén)教程之三重斜線指令的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-10-10探索Emberjs制作一個(gè)簡(jiǎn)單的Todo應(yīng)用
使用Emberjs制作一個(gè)簡(jiǎn)單的Todo應(yīng)用,需要的朋友可以參考下2012-11-11