這篇文章給大家分享的是有關javascript數據結構之多叉樹經典操作的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
多叉樹可以實現復雜的數據結構的存儲，通過遍歷方法可以方便高效的查找數據，提高查找的效率，同時方便管理節點數據。javascript的DOM其實就是以多叉樹的形式存儲的。下面用javascript來實現多叉樹的數據結構
1、創造一個節點
數據是以節點的形式存儲的：
class Node {
constructor(data) {
this.data = data;
this.parent = null;
this.children = [];
}
}2、創造樹
樹用來連接節點，就像真實世界樹的主干一樣，延伸著很多分支
class MultiwayTree {
constructor() {
this._root = null;
}
}3、添加一個節點
function add(data, toData, traversal) {
let node = new Node(data)
// 第一次添加到根節點
// 返回值為this，便于鏈式添加節點
if (this._root === null) {
this._root = node;
return this;
}
let parent = null,
callback = function(node) {
if (node.data === toData) {
parent = node;
return true;
}
};
// 根據遍歷方法查找父節點（遍歷方法后面會講到），然后把節點添加到父節點
// 的children數組里
// 查找方法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、深度優先遍歷
深度優先會盡量先從子節點查找，子節點查找完再從兄弟節點查找，適合數據深度比較大的情況，如文件目錄
function 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();
}
}
}5、廣度優先遍歷
廣度優先遍歷會優先查找兄弟節點，一層層往下找，適合子項較多情況，如公司崗位級別
function 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();
}
}
}6、包含節點
function contains(callback, traversal) {
traversal.call(this, callback);
}回調函數算法可自己根據情況實現，靈活度較高
7、移除節點
// 返回被移除的節點
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實現:
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;
}
//深度優先遍歷
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();
}
}
}
//廣度優先遍歷
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');
// 深度優先查找
console.group('contains1');
tree.contains(function(node) {
console.log(node.data);
if (node.data === 'f') {
return true;
}
}, tree.traverseDF);
console.groupEnd('contains1')
// 廣度優先查找
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數據結構之多叉樹經典操作的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
