从 JS 数组创建树结构

Question

我正在尝试从列表中创建树。我的数据如下；

A-->B-->C-->D-->E..
A-->B-->C-->D-->F..
A-->F-->C-->D-->E..
.
.
.

我有一个包含所有可能的数据路径的数组。我想以以下方式展示它：

                     A
                       -B
                         -C
                           -D 
                              -E
                              -F
                       -F
                         -C
                           -D
                             -E 

我该如何使用JavaScript创建并检查树形结构？我需要创建树形结构的函数 :)

function parseData(data)
  {


   $.each(data, function (i, p) {
                   var arr = p.split("--->");

                 createTreeFunction(p);

                  });

   };
  function parseData(data)
      {


       $.each(data, function (i, p) {
                       var arr = p.split("--->");

                     createTreeFunction(p);

                      });

   };

- s.aslan

---

JavaScript != Java，这个网站上无数次都有提到。 - Rabbit Guy

请提供一些有效的数据（树形结构），或创建一个循环。请使用唯一标识符。 - Nina Scholz

Answer 1

对于构建树形结构的子节点，你至少可以使用两种不同的数据结构，一种是数组（解决方案A），另一种是对象（解决方案B）。

与对象相比，数组的优点是可以直接迭代其子节点。而对于对象，您需要先获取键，然后才能进行迭代。

另外，如果您知道其中一个子节点，则通过键访问速度更快。这也适用于向树中插入新节点。

对于子节点数组，您需要使用 getChild 函数来测试是否存在某个子节点。

_{注意，提供的数据没有保持标识符唯一。}

使用数组作为子节点的解决方案A：

function Node(id) {
    this.id = id;
    this.children = []; // array
}

Node.prototype.getChild = function (id) {
    var node;
    this.children.some(function (n) {
        if (n.id === id) {
            node = n;
            return true;
        }
    });
    return node;
};

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        var node = r.getChild(b);
        if (!node) {
            node = new Node(b);
            r.children.push(node);
        }
        return node;
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);

<pre id="out"></pre>

使用对象为子元素的解决方案B：

function Node(id) {
    this.id = id;
    this.children = {}; // object
}

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        if (!r.children[b]) {
            r.children[b] = new Node(b);
        }
        return r.children[b];
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);

<pre id="out"></pre>

两个提案都使用了 Array#forEach 和 Array#reduce 来迭代给定的字符串，并返回实际id的引用。如果找不到id，则取一个新的节点实例并添加到数组或对象中。引用被返回以进行下一次id检查。

- Nina Scholz

---

我看到你对 console.log() 不满意，开始使用更酷的显示方法来处理嵌套的东西。对你的解决方案点个赞。 - Redu

@Redu，是的，这个区域太小了，无法显示更大的数据结构。 - Nina Scholz

Answer 2

在这种情况下，我发明了两个非常有用的对象方法，即Object.prototype.getNestedValue()和Object.prototype.setNestedValue()。通过利用这些方法，这项工作只需要一行JS代码即可完成。请参见以下内容...

Object.prototype.getNestedValue = function(...a) {
  return a.length > 1 ? (this[a[0]] !== void 0 && this[a[0]].getNestedValue(...a.slice(1))) : this[a[0]];
};
Object.prototype.setNestedValue = function(...a) {
  return a.length > 2 ? typeof this[a[0]] === "object" && this[a[0]] !== null ? this[a[0]].setNestedValue(...a.slice(1))
                                                                              : (this[a[0]] = typeof a[1] === "string" ? {} : new Array(a[1]),
                                                                                 this[a[0]].setNestedValue(...a.slice(1)))
                      : this[a[0]] = a[1];
};

var data = "A-->B-->C-->D-->E\nA-->B-->C-->D-->F\nA-->F-->C-->D-->E",
  datarr = data.split("\n").map(e => e.split("-->")), // get your list in an array
       o = {};
datarr.forEach(a => !o.getNestedValue(...a) && o.setNestedValue(...a,null));

console.log(JSON.stringify(o,null,2));

- Redu