Javascript 递归导致循环结构

Question

我有以下二维数组cells:

ID  Name    Parent
1   Bob     0
2   Alice   1
3   John    2
4   Jane    2
5   Jenny   3
6   Jonny   2

我想将其转换为嵌套的 JSON 格式，这样每个 object 都具有以下属性：

姓名
children 的数组，其中还包括 object 的名称和 children 的数组。数组中没有循环嵌套； a child 不能有任何 parents 作为 children.

下面是我写的函数：

function getChildren(node){
    console.log('Getting Children for' + node)
    children = []
    for(i = 0;i < cells.length; i++){
        if(cells[i][2] == node){
            cell = cells[i]
            child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }
    }
    return children
}


text = "ID  Name    Parent\n1   Bob     0\n2   Alice   1\n3   John                  2\n4   Jane    2\n5   Jenny     3\n6   Jonny   2\n"

lines = text.split('\n')
cells = []
for(i = 0; i < lines.length; i++){
    cells[i] = lines[i].split(/\ +/)
}

在节点 6 getChildren(6) 上调用函数，得到以下输出：

Getting Children for6
[]

这是正确的，因为节点 6 没有 children.

但是在 children 节点上调用函数，例如 getChildren(3)，给出：

Getting Children for3
Getting Children for5

Object
    children: Array[1]
        0: Object
            children: Array[1]
                0: Object
                    children: Array[1]
                    name: "Jenny"
                    length: 1
            name: "Jenny"
            length: 1
    name: "Jenny"

从控制台输出看来它调用了正确的函数，但为什么 "jenny" 的 object 无限嵌套在所有 children 下？

我想以 JSON object 结束，我可以在 JSON.stringify 上使用它。在 getChildren(3) 上调用函数给出错误

Uncaught TypeError: Converting circular structure to JSON.

我认为这是因为 Jenny 的 object 无限嵌套在每个 child 下。

Answer 1

将您的函数更改为以下内容

function getChildren(node){
    console.log('Getting Children for' + node)
    var children = []
    for(i = 0;i<cells.length; i++){
        if(cells[i][2] == node){
            var cell = cells[i]
            child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }}
    return children
}

注意在变量声明之前添加的 "var"。这确保它们被重新初始化，而不是通过函数调用持久化。这就是导致您出现问题的原因。

Answer 2

你使用了全局变量，因此，当你递归调用你的函数时，像 children 和 child 这样的变量可以得到新的值。当你退出递归调用时，你会做：

children.push(child)

.. 但是 children 会取与您预期不同的值，因此 child 也可以有不同的值，两者都来自它们在递归调用中是什么（或者从递归的更深处）。

同理递归修改i也会出问题

使用 var 使您的变量成为函数的局部变量，它将起作用：

function getChildren(node){
    console.log('Getting Children for' + node)
    var children = []
    for(var i = 0;i<cells.length; i++){
        if(cells[i][2] == node){
            var cell = cells[i]
            var child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }}
    return children
}

function getChildren(node){
    var children = []
    for(var i = 0;i<cells.length; i++){
        if(cells[i][2] == node){
            var cell = cells[i]
            var child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }}
    return children
}

var text = "ID  Name    Parent\n1   Bob     0\n2   Alice   1\n3   John                  2\n4   Jane    2\n5   Jenny     3\n6   Jonny   2\n"

var lines = text.split('\n')
var cells = []
for(var i = 0; i< lines.length; i++){
  cells[i] = lines[i].split(/\ +/)
}

console.log(JSON.stringify(getChildren(0), null, 2));

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

Answer 3

如果我没理解错的话，您可以使用另一种方式来解析您的数据：

//separete the values
var input = [
    [1,   'Bob',     0],
    [2,   'Alice',   1],
    [3,   'John',    2],
    [4,   'Jane',    2],
    [5,   'Jenny',   3],
    [6,   'Jonny',   2]
];

var entities = []; //I belive that the ids are uniq

for (var i = 0; i < input.length; i++){
    var id = input[i][0];
  entities[id] = {
    id: id, 
    name: input[i][1], 
    children : [], 
    parent: input[i][2]
  };
}

for (var i in entities){
    var current = entities[i];
  var parent = entities[current.parent];
  delete current.parent;

  if (parent){
        parent.children.push(current);
  }
}

通过这种方式，您可以通过索引从实体数组中找到特定元素，或者在解析开始时获取根元素（元素数组中不包含其父元素的元素）

Javascript 递归导致循环结构

Javascript recursion caused circular structure

javascript

recursion

json

infinite