图表中使用三元组构建树及其反过程的算法

题目一

假设数据结构如下:

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: 0,
    value: 0,
    children: [
        {
            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: [ ]
                }
            ]
        }
    ]
}

分析:我们首先要得到父子关系,利用引用关系,我们很容易可以重构,参考代码如下:

function shapeToTree(data) {
    var nodes = {}, edges = {};
    // 找到id对应的值
    data.forEach( function(val, index) {
        //找到id对应的节点
        nodes[val['id']] = new Node(val['id'], val['value'], []);
        //找到父子关系
        edges[val['parentId']]
        ? edges[val['parentId']].push(val['id'])
        : edges[val['parentId']] = [val['id']];
    });
    //找到根节点
    var rootId = 0;
    Object.keys(edges).forEach( function(key, index) {
        if(!key in nodes) rootId = key;
    });
    nodes[rootId] = new Node(rootId, 0, []);
    //遍历
    Object.keys(edges).forEach( function(key, index) {
        if(!key in nodes) rootId = key;
        edges[key].forEach( function(element, index) {
            nodes[key].children.push(nodes[element])
        });
    });
    return nodes[rootId];
}

题目二

假设数据结构如下:

var node = {
    name: 'root',
    children: [
    {
        name: 'item-1', children: [{name: 'item-1-1', children: []}, {name: 'item-1-2', children: []}]
    },
    {
        name: 'item-2', children: [{name: 'item-2-1', children: []}, {name: 'item-2-2', children: []}]
    },
    {
        name: 'item-3', children: [{name: 'item-3-1', children: []}, {name: 'item-3-2', children: []}]
    }
    ]
}

要求使用广度优先算法得到以下结果

[ 'root',
  'item-1',
  'item-2',
  'item-3',
  'item-1-1',
  'item-1-2',
  'item-2-1',
  'item-2-2',
  'item-3-1',
  'item-3-2' ]

分析:这道题可以看成层次遍历树的一个变型,通过一个缓存数组可以实现层次遍历,一种参考写法如下:

function traversal(data) {
    if(data == null || !data['name']) {
        return []
    }
    var names = [], tmp = [data]
    while (tmp.length > 0) {
        var node = tmp.shift()
        names.push(node['name'])
        node['children'].forEach(function (val) {
            tmp.push(val)
        })
    }
    return names
}

 上一篇
React项目实战(一)起手式 React项目实战(一)起手式
安装npx create-react-app react-juejin cd react-juejin yarn add antd-mobile rc-form react-loadable react-redux yarn add -D
2019-03-13
下一篇 
React学习(四)实现组件关注分离 React学习(四)实现组件关注分离
Container-Component模式在开发中,可能会经常遇到两个页面或者区域展示的文档结构和样式是相同的,但数据源和交互不同。该情况下如何左到最大化的功能复用呢?——将展示部分抽离,数据和交互部分分开 Container:容器组件,
2019-02-23
  目录