Как сделать массив массивов из структуры данных дерева в JavaScript?

Question

как преобразовать приведенную выше структуру данных в

[['Tywin'],['Jamie','Cersi', 'Tyrion'], ['Joeffry', 'Myrcella', 'Tomen', 'Lin']]

Вот мой код:

let Tree = function(name) {
  this.name = name;
  this.children = [];
}

Tree.prototype.addChild = function(parent, name) {
  const node = lannister.contains(parent);
  node.children.push(new Tree(name));
}

var lannister = new Tree('Tywin');

lannister.addChild('Tywin', 'Jamie');
lannister.addChild('Tywin', 'Cersi');
lannister.addChild('Tywin', 'Tyrion');
lannister.addChild('Cersi', 'Joffery');
lannister.addChild('Cersi', 'Myrcella');
lannister.addChild('Cersi', 'Tomen');
lannister.addChild('Tyrion', 'Lin');
bfs();

function bfs(check) {
  //   console.log('traverseBFS called: ', this);
  bfsArray = [];
  var queue = [this];
  var node;
  var tempAr = [];
  bfsArray.push([this.name]);

  while (queue.length > 0) {
    node = queue.shift();
    callback(node.name, node.children.length);
    console.log('current node is: ', node, node.children.length);

    for (var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
      tempAr.push(node.children[i].name);
      if (i === node.children.length - 1) {
        // console.log('The bfs is ', bfsArray, tempAr);
        bfsArray.push(tempAr);
        tempAr = [];
      }
    }
  }

  function callback(itm, length) {

    // console.log('itm is: ', itm);
    if (itm === check) {
      node;
    }
  }
};

Answer 1

Вы можете использовать массив и рекурсивную функцию, которая хранит уровень и переводит имена на соответствующий уровень.

function Node(name) {
    this.name = name;
    this.children = [];
}

function Tree(name) {
    this.tree = new Node(name);
}

Tree.prototype.addChild = function (parent, child) {
    function findParent(node) {
        var found;
        if (node.name === parent) return node;
        node.children.some(n => found = findParent(n));
        return found;
    }
    var node = findParent(this.tree) || this.tree;
    node.children.push(new Node(child));
};

Tree.prototype.BST = function () {
    const getNodes = (level = 0) => node => {
        levels[level] = levels[level] || [];
        levels[level].push(node.name);
        node.children.forEach(getNodes(level + 1));
    };

    var levels = [];
    getNodes()(this.tree);
    return levels;
}

var lannister = new Tree('Tywin');

lannister.addChild('Tywin', 'Jamie');
lannister.addChild('Tywin', 'Cersi');
lannister.addChild('Tywin', 'Tyrion');
lannister.addChild('Cersi', 'Joffery');
lannister.addChild('Cersi', 'Myrcella');
lannister.addChild('Cersi', 'Tomen');
lannister.addChild('Tyrion', 'Lin');

console.log(lannister.BST());
console.log(lannister);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Грязное решение: используйте объект как древовидную структуру и сохраняйте имена символов в ключах объектов.

let family_tree = {
   Jamie: {},
   Cersei: {Joeffry: {}, Myrcella: {}, Tomen: {}},
   Tyrion: {Lin: {}}
}

Если вам нужно перебрать объект, используйте метод Object.keys(family_tree).