資訊專欄INFORMATION COLUMN
簡單的遍歷一個樹形結(jié)構(gòu)數(shù)據(jù)的幾種方法、非遞歸方法效率最好。
(function (window, undefined) {
var treeNodes = [
{
id: 1,
name: "1",
children: [
{
id: 11,
name: "11",
children: [
{
id: 111,
name: "111",
children:[]
},
{
id: 112,
name: "112"
}
]
},
{
id: 12,
name: "12",
children: []
}
],
users: []
},
{
id: 2,
name: "2",
children: [
{
id: 22,
name: "22",
children: []
}
]
}
];
//遞歸實(shí)現(xiàn)
var parseTreeJson = function(treeNodes){
if (!treeNodes || !treeNodes.length) return;
for (var i = 0, len = treeNodes.length; i < len; i++) {
var childs = treeNodes[i].children;
console.log(treeNodes[i].id);
if(childs && childs.length > 0){
parseTreeJson(childs);
}
}
};
console.log("------------- 遞歸實(shí)現(xiàn) ------------------");
parseTreeJson(treeNodes);
//非遞歸廣度優(yōu)先實(shí)現(xiàn)
var iterator1 = function (treeNodes) {
if (!treeNodes || !treeNodes.length) return;
var stack = [];
//先將第一層節(jié)點(diǎn)放入棧
for (var i = 0, len = treeNodes.length; i < len; i++) {
stack.push(treeNodes[i]);
}
var item;
while (stack.length) {
item = stack.shift();
console.log(item.id);
//如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，繼續(xù)添加進(jìn)入棧底
if (item.children && item.children.length) {
//len = item.children.length;
// for (i = 0; i < len; i++) {
// stack.push(item.children[i]);
// }
stack = stack.concat(item.children);
}
}
};
console.log("------------- 非遞歸廣度優(yōu)先實(shí)現(xiàn) ------------------");
iterator1(treeNodes);
//非遞歸深度優(yōu)先實(shí)現(xiàn)
var iterator2 = function (treeNodes) {
if (!treeNodes || !treeNodes.length) return;
var stack = [];
//先將第一層節(jié)點(diǎn)放入棧
for (var i = 0, len = treeNodes.length; i < len; i++) {
stack.push(treeNodes[i]);
}
var item;
while (stack.length) {
item = stack.shift();
console.log(item.id);
//如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，繼續(xù)添加進(jìn)入棧頂
if (item.children && item.children.length) {
// len = item.children.length;
// for (; len; len--) {
// stack.unshift(item.children[len - 1]);
// }
stack = item.children.concat(stack);
}
}
};
console.log("------------- 非遞歸深度優(yōu)先實(shí)現(xiàn) ------------------");
iterator2(treeNodes);
})(window);
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/91521.html
前天面試遇到一個多叉樹面試的題目，在這里分享記錄一下。 題目：一個樹形的數(shù)據(jù)(如下數(shù)據(jù))，面試官給你一個id，然后拿到對應(yīng)的name? 數(shù)據(jù)結(jié)構(gòu)大概是這個樣子 var cityData = [ { id: 1, name: 廣東省, children: [ { id: 11, ...
摘要：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等中序遍歷可以實(shí)現(xiàn)表達(dá)式樹，在編譯器底層很有用后序遍歷可以用來實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。 樹的簡介 棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹是非順序數(shù)據(jù)結(jié)構(gòu)。樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)...
閱讀 2958·2021-11-24 09:39
閱讀 2869·2021-09-29 09:34
閱讀 3560·2021-09-24 10:23
閱讀 1746·2021-09-22 15:41
閱讀 1701·2019-08-30 15:55
閱讀 3516·2019-08-30 13:58
閱讀 2624·2019-08-30 13:11
閱讀 1669·2019-08-29 12:31
