以类似的方式打印树结构,存储缩进字符串(由┣,┃,┗组成)

Question

我想为每个对象存储"节点缩进字符串",如下所示:

foo
?bar
??baz
? ?qux
?  ?quux
?  ?corge
?fizz
?buzz

给出每个对象的数据:

objects = [
{'id':1,'parent_id':null, 'name':'foo'}
{'id':2,'parent_id':1, 'name':'bar'}
];

请注意,我不想打印任何内容,我只想将indent每个对象的字符数组计算出来:

{'id':6,'parent_id':4, 'name':'corge', 'indent':['?',' ',' ','?']}

到目前为止,我只能用空格缩进它们但没有"管道",我很难想出一个解决方案.有帮助吗？

如果有帮助,我正在使用JS和Angular.

编辑:根据要求我到目前为止的代码.我最初没有发布这个,因为我觉得这是一个错误的基础/方法来构建.它的工作原理非常简单:对于每个对象,计算它的祖先并相应地添加它们" ".

// go through all our objects and set their indent strings
setIndents = function()
{
    for (var x in objects) {
        var o = objects[x];
        o.nodes = [];

        // push space character for amount of ancestors
        numParents = countParents(o, 0);
        for (var i = 0; i < numParents; i++)
            o.nodes.push(" ");
    }
};
// recursively counts how many ancestors until we hit the root
countParents = function(current, count)
{
    if (current.parent_id !== null) {
        for (var x in objects) {
            if (objects[x].id == current.parent_id) {
                current = objects[x]; //set as new current
                count++;
                break;
            }
        }
        return countParents(current, count);
    } else {
        return count;
    }

};

Answer 1

正如@JBCP所指出的那样(见评论)我的原始代码存在一个严重的缺陷,如果最初的订单不完美,那将会破坏整个事情.

所以这里是一个更新版本,元素的顺序现在可以是随机的(它仍然扮演一个角色,它间接定义子命令,但树结构将是正确的).

我还拆分了这些功能,以便更好地配置它们.例如treeIndent现在预计一个节点分支所产生treeify.(注意:该shuffle功能仅用于测试订单独立性)

'use strict';

/**
 * @see https://bost.ocks.org/mike/shuffle/
 *
 * @param array
 * @returns {*}
 */
function shuffle(array) {
    var m = array.length, t, i;

    // While there remain elements to shuffle…
    while (m) {
        // Pick a remaining element…
        i = Math.floor(Math.random() * m--);

        // And swap it with the current element.
        t = array[m];
        array[m] = array[i];
        array[i] = t;
    }

    return array;
}

function treeify(flat) {
    var map = { __root__: { children: [] }};

    flat.forEach(function (node) {
        var
            parentId = node.parent_id || '__root__',
            id = node.id;

        // init parent
        if (!map.hasOwnProperty(parentId)) {
            map[parentId] = { element: null, children: [] };
        }

        // init self
        if (!map.hasOwnProperty(id)) {
            map[id] = { element: null, children: [] };
        }

        map[id].element = node;
        map[parentId].children.push(map[id]);
    });

    return map.__root__.children;
}

function treeIndent(branch, cfg, decorator, indent)
{
    indent = indent || [];

    branch.forEach(function (node, i) {
        decorator(node.element, indent.concat(
            i === branch.length - 1 ? cfg.isLastChild : cfg.hasNextSibling
        ));

        treeIndent(node.children, cfg, decorator, indent.concat(
            i === branch.length - 1 ? cfg.ancestorIsLastChild : cfg.ancestorHasNextSibling
        ));
    });
}

var input = [
    { id: 1, parent_id: null,              name: 'root'  },
        { id: 2, parent_id: 1,             name: 'bar'   },
            { id: 5, parent_id: 2,         name: 'baz'   },
                { id: 6, parent_id: 5,     name: 'qux'   },
                    { id: 7, parent_id: 6, name: 'quux'  },
                    { id: 8, parent_id: 6, name: 'corge' },
            { id: 9, parent_id: 2,         name: 'but'   },
        { id: 3, parent_id: 1,             name: 'fizz'  },
        { id: 4, parent_id: 1,             name: 'buzz'  }
];

var log = document.getElementById('log');

treeIndent(treeify(shuffle(input)), {
    hasNextSibling:         '├',
    isLastChild:            '└',
    ancestorHasNextSibling: '│',
    ancestorIsLastChild:    ' '
}, function (element, indent) {
    log.innerHTML += indent.join(' ') + ' ' + element.name + "\n";
});

<pre id="log"></pre>

老答案(坏了!):

尝试以下方法:

function makeTree(flat) {
  var map = { __root__: { children: [] }};

  flat.forEach(function (node) {
    var
      parentId = node.parent_id || '__root__',
      id = node.id;

    // init parent
    if (!map.hasOwnProperty(parentId)) {
      map[parentId] = { children: [] };
    }

    // init self
    if (!map.hasOwnProperty(id)) {
      map[id] = { children: [] };
    }

    map[id].element = node;
    map[parentId].children.push(map[id]);
  });

  return map.__root__.children;
}

function injectTreeIndent(input) {
  var
    levelMap = [],
    indicators = {
      hasNextSibling:         '?',
      isLastChild:            '?',
      ancestorHasNextSibling: '?',
      ancestorIsLastChild:    ' '
    }
  ;

  // apply `indent`
  (function traverse(branch, depth) {
    branch.forEach(function (node, idx) {
      node.element.indent = levelMap.map(function (ancestor) {
        return ancestor === indicators.hasNextSibling ? indicators.ancestorHasNextSibling : indicators.ancestorIsLastChild;
      });

      // if (depth > 0) { // uncomment this, if root elements should have no indentation
      node.element.indent.push(
        levelMap[depth] = branch.length - 1 > idx ? indicators.hasNextSibling : indicators.isLastChild
      );
      // }

      traverse(node.children, depth + 1);

      levelMap.pop();
    });
  }(makeTree(input), 0));
}

var input = [
  { id: 1, parent_id: null, name: 'foo'   },
  { id: 2, parent_id: 1,    name: 'bar'   },
  { id: 5, parent_id: 2,    name: 'baz'   },
  { id: 6, parent_id: 5,    name: 'qux'   },
  { id: 7, parent_id: 6,    name: 'quux'  },
  { id: 8, parent_id: 6,    name: 'corge' },
  { id: 3, parent_id: 1,    name: 'fizz'  },
  { id: 4, parent_id: 1,    name: 'buzz'  }
];

injectTreeIndent(input);

• makeTree 用于获取从给定的平面数据派生的嵌套结构.
• injectTreeIndent 然后遍历该嵌套结构以注入所需的缩进信息.

演示:http://jsfiddle.net/6R7wf/1/

没有缩进的根元素演示:http://jsfiddle.net/zMY7v/