前端筆試中兩道與節(jié)點(diǎn)有關(guān)的算法題

荊兆峰發(fā)布于2019-08-26 13:37 / 3209人閱讀

摘要：分別用廣度優(yōu)先遍歷和深度優(yōu)先遍歷展開下面節(jié)點(diǎn)示例廣度優(yōu)先遍歷輸出結(jié)果深度優(yōu)先遍歷輸出結(jié)果關(guān)系型數(shù)組轉(zhuǎn)換成樹形結(jié)構(gòu)對象類似期望輸出代碼

1.分別用廣度優(yōu)先遍歷和深度優(yōu)先遍歷展開下面節(jié)點(diǎn)

示例

var tree = {
    name: "root",
    children: [{
        name: "child1",
        children: [{
            name: "child1_1",
            children: []
        }, { name: "child1_2", children: [] }]
    }, {
        name: "child2",
        children: [{
            name: "child2_1",
            children: []
        }]
    }, {
        name: "child3",
        children: [{
            name: "child2_1",
            children: []
        }]
    }]
};

廣度優(yōu)先遍歷：

function wideTraversal(node) {
    var nodes = [];
    if (node != null) {
        var queue = [];
        queue.unshift(node);
        while (queue.length != 0) {
            var item = queue.shift();
            nodes.push(item.name);
            var children = item.children;
            for (var i = 0; i < children.length; i++) {

                queue.push(children[i]);
            }
        }

    }
    return nodes;
}
console.log(wideTraversal(tree))

輸出結(jié)果：

[ "root","child1","child2","child3","child1_1","child1_2","child2_1","child2_1" ]

深度優(yōu)先遍歷：

function traverseTree(node) {
    var child = node.children,
        arr = [];

    arr.push(node.name);
    if (child) {
        child.forEach(function(node) {
            arr = arr.concat(traverseTree(node));
        });
    }
    return arr;
}
console.log(traverseTree(tree))

輸出結(jié)果：

[ "root","child1","child1_1","child1_2","child2","child2_1","child3","child2_1" ]

2.關(guān)系型數(shù)組轉(zhuǎn)換成樹形結(jié)構(gòu)對象

類似：

var data = [
    { parentId: 0, id: 1, value: "1" },
    { parentId: 3, id: 2, value: "2" },
    { parentId: 0, id: 3, value: "3" },
    { parentId: 1, id: 4, value: "4" },
    { parentId: 1, id: 5, value: "5" }
]

期望輸出：

[
{id:1,value:"1",
children:[{id:4,value:"4",children:[]},
{id:5,value:"5",children:[]}]},
{id:3,value:"3",
children:[id:2,value:"2",children:[]]}]

代碼：

var getJsonTree = function(data, parentId) {
    var itemArr = [];
    for (var i = 0; i < data.length; i++) {
        var node = data[i];
        //data.splice(i, 1)
        if (node.parentId == parentId) {
            var newNode = { id: node.id, value: node.value, children: getJsonTree(data, node.id) };
            itemArr.push(newNode);
        }
    }
    return itemArr;
}
console.log(getJsonTree(data, 0))