Javascript无限类别深度树

Question

我正在尝试生成一棵平面数组树，将子类别放置在父类别旁边，但很难做同样的事情。

var categories = [
  {
    name: 'Javascript'
  },
  {
    name: 'jQuery',
    parent: 'Javascript'
  },
  {
    name: 'AngularUi',
    parent: 'Angular'
  },
  {
    name: 'Angular',
    parent: 'Javascript'
  },
  {
    name: 'D3',
    parent: 'Javascript'
  }
];

var tree = [];

function getChilds(array,identifier){
    return _.filter(array,function(val){
        return val.parent == identifier
    });
}

function createTree(array){
    for(var x=0;x<_.size(array);x++){
      tree.push(array[x].name);
      var childs = getChilds(array,array[x].name);
        if(_.size(childs) > 0){
          createTree(childs);
        }else{
          $('div').append(JSON.stringify(tree));
        }
    }
}

createTree(categories);

<script src="http://underscorejs.org/underscore-min.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div></div>

预期输出

['Javascript','Jquery','Angular','AngularUi','D3']

这是我到目前为止所尝试过的，使用下划线几乎没有帮助。任何帮助将不胜感激 。

Answer 1

我不知道你为什么要这样做(你所描述的结果根本不是一棵树)，但以下将提供你所描述的结果:

function addChildren(source, identifier, dest) {
  source.filter(function(val) {
    return val.parent == identifier;
  }).forEach(function(val) {
    dest.push(val.name);
    addChildren(source, val.name, dest);
  });
}

function buildTree(source) {
  var dest = [];
  addChildren(source, undefined, dest);
  return dest;
}

var categories = [{
  name: 'Javascript'
}, {
  name: 'jQuery',
  parent: 'Javascript'
}, {
  name: 'AngularUi',
  parent: 'Angular'
}, {
  name: 'Angular',
  parent: 'Javascript'
}, {
  name: 'D3',
  parent: 'Javascript'
}];


var tree = buildTree(categories);

请注意，上面使用 filter 的方法是一个 O(N²) 操作(效率非常低)。

您可以通过首先使用_.groupBy对源数组进行索引来将其更改为O(N)操作:

function addChildren(index, identifier, dest) {
    (index[identifier] || []).forEach(function (val) {
        dest.push(val.name);
        addChildren(index, val.name, dest);
    });
}

function buildTree(source) {
    var dest = [];
    addChildren(_.groupBy(source, 'parent'), undefined, dest);
    return dest;
}

var categories = [{
    name: 'Javascript'
}, {
    name: 'jQuery',
    parent: 'Javascript'
}, {
    name: 'AngularUi',
    parent: 'Angular'
}, {
    name: 'Angular',
    parent: 'Javascript'
}, {
    name: 'D3',
    parent: 'Javascript'
}];

var tree = buildTree(categories);
console.log(tree);

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.7.0/underscore-min.js"></script>