javascript - Printing a tree structure in a list like manner, storing the indent strings (which consist of┣, ┃, ┗ ) - Stack Over

admin管理员组

文章数量:1317894

I want to store the "node indentation string" for each object, something like this:

foo
┣bar
┃┗baz
┃ ┗qux
┃  ┣quux
┃  ┗corge
┣fizz
┗buzz

Given data for each object:

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

Note that I don't want to print anything, I just want to work out the indent as an array of characters for each object:

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

So far I can only indent them with spaces but no 'pipes' and I am stumped at ing up with a solution. Any help?

I am using JS with Angular if it helps.

EDIT: As requested the code I have so far. I didn't post this at first because I felt that it's a wrong foundation/approach to build on. How it works is pretty trivial: for each object, count it's ancestors and add " "'s accordingly.

// 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;
    }

};

I want to store the "node indentation string" for each object, something like this:

foo
┣bar
┃┗baz
┃ ┗qux
┃  ┣quux
┃  ┗corge
┣fizz
┗buzz

Given data for each object:

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

Note that I don't want to print anything, I just want to work out the indent as an array of characters for each object:

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

So far I can only indent them with spaces but no 'pipes' and I am stumped at ing up with a solution. Any help?

I am using JS with Angular if it helps.

EDIT: As requested the code I have so far. I didn't post this at first because I felt that it's a wrong foundation/approach to build on. How it works is pretty trivial: for each object, count it's ancestors and add " "'s accordingly.

// 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;
    }

};

• javascript
• tree

Share Improve this question Follow edited Feb 26, 2014 at 13:06 tiffanyhwang asked Feb 26, 2014 at 10:13 tiffanyhwangtiffanyhwang 1,45355 gold badges1818 silver badges2828 bronze badges 2

• Would you also add your existing code that creates the indents? This will allow for suggestions on how to improve it – stackh34p Commented Feb 26, 2014 at 11:11
• @IvayloSlavov yes, absolutely. – tiffanyhwang Commented Feb 26, 2014 at 11:44

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 7

As @JBCP pointed out (see ments) there is a serious flaw in my original code that would break the whole thing if the initial order was anything but perfect.

So here's an updated version, the order of elements can now be random (it still plays a role in such that it indirectly defines the children order, but the tree-structure will be correct).

I also split the functions so that they can be better configured. For example treeIndent now expects a node branch produced by treeify. (Note: the shuffle function is just there to test the order independence)

'use strict';

/**
 * @see https://bost.ocks/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>

---

Old answer (broken!):

try the following:

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) { // unment 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 is used to optain a nested structure derived from the given flat data.
• injectTreeIndent then traverses that nested structure to inject the required indent informatoin.

demo: http://jsfiddle/6R7wf/1/

demo with root elements having no indenation: http://jsfiddle/zMY7v/

After for (var i = 0; i < numParents; i++) o.nodes.push(" ");, try

if (o.nodes.length === 1)
    o.nodes[0] = "┣";
else if (o.nodes.length > 1) {
    o.nodes[0] = "┃";
    o.nodes[o.nodes.length - 1] = "┗";
}

const addIndents = objects => {
  objects.forEach(o => o.children = objects.filter(o2 => o2.parent_id === o.id));
  const roots = objects.filter(o => !objects.some(o2 => o2.children.includes(o)));
  roots.forEach(o => addTree(o));
};

const PFXs = { true: { true: " ", false: "┃" }, false: { true: "┗", false: "┣" }};
const addTree = (t, levels = []) => {
  t.indent = levels.map((p, i) => PFXs[i < levels.length - 1][p]);
  t.children?.forEach((x, i) => addTree(x, [...levels, i === t.children.length-1]));
};

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

addIndents(objects);

objects.forEach(o => console.log(o.indent.join("") + o.name))

本文标签：