将数据排序到树中

Question

我有以下数据:

var data = [
    { index : 1, sort : 10, parent : 0 },
    { index : 2, sort : 7, parent : 0 },
    { index : 3, sort : 15, parent : 1 },
    { index : 4, sort : 4, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 6, sort : 20, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 8, sort : 6, parent : 5 },
];

如何通过父ID和排序值对其进行有效排序,以便最终得到:

var data = [
    { index : 4, sort : 4, parent : 0 },    
    { index : 2, sort : 7, parent : 0 },
    { index : 1, sort : 10, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 8, sort : 6, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 6, sort : 20, parent : 5 },   
    { index : 3, sort : 15, parent : 1 },
];

这是一种树形结构.每个元素后面紧跟着任何子元素,同一分支上的所有元素都按排序值排序.

我能想到的最好的方法是先按父级排序,然后对每个分支进行第二次排序.这似乎效率低下.

编辑:示例排序顺序错误.我已经纠正过了.

编辑以供说明:每个嵌套分支都需要显示在父值的正下方,而不是在分支的末尾.

编辑:对数据的进一步更正.

Answer 1

这不是您的原始方法,但您可以根据数据构建实际树,如下所示:

function TreeNode(data) {
  this.data     = data;
  this.parent   = null;
  this.children = [];
}
TreeNode.comparer = function (a, b) { 
  return a.data.sort < b.data.sort ? 0 : 1; 
};
TreeNode.prototype.sortRecursive = function () {
  this.children.sort(TreeNode.comparer);
  for (var i=0, l=this.children.length; i<l; i++) {
    this.children[i].sortRecursive();
  }
  return this;
};

function toTree(data) {
  var nodeById = {}, i = 0, l = data.length, node;

  nodeById[0] = new TreeNode(); // that's the root node

  for (i=0; i<l; i++) {  // make TreeNode objects for each item
    nodeById[ data[i].index ] = new TreeNode(data[i]);
  }
  for (i=0; i<l; i++) {  // link all TreeNode objects
    node = nodeById[ data[i].index ];
    node.parent = nodeById[node.data.parent];
    node.parent.children.push(node);
  }
  return nodeById[0].sortRecursive();
}

通过这种设置,您可以通过简单的调用整齐地嵌套节点:

var tree = toTree(data);

TreeNode:0
  parent  -> null
  data    -> undefined
  childen -> Array[
    TreeNode:1
      parent  -> TreeNode:0
      data    -> { index : 4, sort :  4, parent : 0 }
      childen -> Array[]
    TreeNode:2
      parent  -> TreeNode:0
      data    -> { index : 2, sort :  7, parent : 0 }
      childen -> Array[]
    TreeNode:3
      parent  -> TreeNode:0
      data    -> { index : 1, sort : 10, parent : 0 }
      childen -> Array[
        TreeNode:4
          parent  -> TreeNode:3
          data    -> { index : 5, sort : 13, parent : 1 }
          childen -> Array[
          ]
        TreeNode:5
          parent  -> TreeNode:3
          data    -> { index : 3, sort : 15, parent : 1 }
          childen -> Array[
            ... and so on ...
          ]
      ]
  ]

拥有该树对象后,您可以使用它执行许多操作,包括以预期顺序递归遍历它.

为此,您可以添加一个辅助函数,该函数执行深度优先遍历并f为每个节点执行有效负载函数:

TreeNode.prototype.walk = function(f, recursive) {
  for (var i=0, l=this.children.length; i<l; i++) {
    var child = this.children[i];
    f.apply(child, Array.prototype.slice.call(arguments, 2));
    if (recursive) child.walk.apply(child, arguments);
  }
}

并称之为:

tree.walk(function () { console.log(this.data) }, true);

会产生:

{ index: 4, sort:  4, parent: 0}
{ index: 2, sort:  7, parent: 0}
{ index: 1, sort: 10, parent: 0}
{ index: 5, sort: 13, parent: 1}
{ index: 8, sort:  6, parent: 5}
{ index: 7, sort:  2, parent: 8}
{ index: 6, sort: 20, parent: 5}
{ index: 3, sort: 15, parent: 1}

将更复杂的有效负载函数用于其他效果,例如将表中的表行与jQuery或项添加到<select>框中.