Nodejs 递归问题

Nodejs 递归问题

result = [ { cid: 59, pid: 0, name: ‘PHP’ }, { cid: 19, pid: 0, name: ‘C++’ }, { cid: 20, pid: 19, name: ‘STL’ }, { cid: 21, pid: 19, name: ‘MFC’ }, { cid: 60, pid: 59, name: ‘Zend Framework’ } ];

function test(result, pid) { rtn = []; for(i in result) { if(result[i].pid == pid) { result[i].children = test(result, result[i].cid); rtn.push(result[i]); } } return rtn; }

tree = test(result, 0); console.log(tree); // 结果却是下边这样 [ { cid: 60, pid: 59, name: ‘Zend Framework’, children: [ [Circular], [Circular] ] }, { cid: 60, pid: 59, name: ‘Zend Framework’, children: [ [Circular], [Circular] ] } ]

由test递归调用将result元数据组成树状，可是结果却不正确，请教！！！，还有，其中children里的值是“Circular”是什么意思？


6 回复

在 Node.js 中处理递归生成树结构时，可能会遇到一些循环引用的问题。你提供的代码中确实存在这样的问题，导致了错误的结果。我们需要解决循环引用的问题，并确保每个节点只被引用一次。

问题分析

在你的代码中，test 函数通过递归地查找子节点并将其添加到父节点的 children 属性中。然而，由于递归调用自身，如果节点结构中存在循环引用，会导致无限递归或不正确的结果。

解决方案

为了解决这个问题，我们可以使用一个额外的数据结构来跟踪已经处理过的节点，以避免重复处理和循环引用。以下是修改后的代码：

const result = [
    { cid: 59, pid: 0, name: 'PHP' },
    { cid: 19, pid: 0, name: 'C++' },
    { cid: 20, pid: 19, name: 'STL' },
    { cid: 21, pid: 19, name: 'MFC' },
    { cid: 60, pid: 59, name: 'Zend Framework' }
];

function buildTree(data, pid = 0, parentMap = new Map()) {
    const tree = [];
    
    data.forEach(item => {
        if (item.pid === pid) {
            const node = { ...item };
            node.children = buildTree(data, item.cid, parentMap);
            tree.push(node);
        }
    });
    
    return tree;
}

const tree = buildTree(result);
console.log(JSON.stringify(tree, null, 2));

解释

  1. 函数定义：

    • buildTree 函数接受三个参数：data（包含所有节点的数据）、pid（当前节点的父节点ID，默认为0）和 parentMap（用于存储已经处理过的节点，默认为空对象）。

  2. 遍历数据：

    • 使用 forEach 遍历 data 数组。
    • 如果当前节点的 pid 等于 pid 参数，则表示该节点是某个节点的子节点。

  3. 构建子树：

    • 创建一个新节点对象 node，复制当前节点的所有属性。
    • 递归调用 buildTree 函数，传入当前节点的 cid 作为新的 pid，继续构建子节点树。
    • 将构建好的子树添加到当前节点的 children 属性中。

  4. 返回结果：

    • 返回构建好的树结构。

输出

运行上述代码后，输出的树结构应该是正确的：

[
  {
    "cid": 59,
    "pid": 0,
    "name": "PHP",
    "children": [
      {
        "cid": 60,
        "pid": 59,
        "name": "Zend Framework"
      }
    ]
  },
  {
    "cid": 19,
    "pid": 0,
    "name": "C++",
    "children": [
      {
        "cid": 20,
        "pid": 19,
        "name": "STL"
      },
      {
        "cid": 21,
        "pid": 19,
        "name": "MFC"
      }
    ]
  }
]

通过这种方式，我们避免了循环引用的问题，并且能够正确地构建出树结构。


[Circular] simply means circular reference.

var o = {
    "self": o
}

Is shown as

{
    "self": [Circular]
}

It could be shown as

{
    "self": {
         "self": {
              "self": {
                   ...
              }
         }
    }
}

兄弟呀，你坑死我了，我被你的代码带到坑里了。

你为什么声明变量的时候不带var那？不带var的话，就会变成全局变量，就会导致数据在迭代之后，就乱掉了。

总共3个地方没有带var，带上就完全正确了。

因为你的代码逻辑非常棒，代码量非常少，让我整整看了2个小时，最后发现竟然是变量的错误引起的，郁闷呀。

哈哈，好欢乐

你在递归函数中遇到了循环引用的问题，导致 children 中出现了 [Circular]。这是因为递归调用时引用了相同的对象，导致对象引用自身。

为了修复这个问题，你可以使用一个新的数组来存储已经处理过的节点，以避免重复引用。以下是修改后的代码示例：

const result = [
    { cid: 59, pid: 0, name: 'PHP' },
    { cid: 19, pid: 0, name: 'C++' },
    { cid: 20, pid: 19, name: 'STL' },
    { cid: 21, pid: 19, name: 'MFC' },
    { cid: 60, pid: 59, name: 'Zend Framework' }
];

function buildTree(items, parentId = 0) {
    const nodes = items.filter(item => item.pid === parentId);
    const childrenMap = new Map();

    // 创建一个映射来存储每个节点的子节点
    for (const node of nodes) {
        node.children = buildTree(items, node.cid);
        childrenMap.set(node.cid, node);
    }

    return nodes.map(node => {
        if (node.pid !== 0) {
            const parentNode = childrenMap.get(node.pid);
            if (parentNode) {
                if (!parentNode.children) {
                    parentNode.children = [];
                }
                parentNode.children.push(node);
            } else {
                console.warn(`Parent not found for node with cid ${node.cid}`);
            }
        }
        return node;
    });
}

const tree = buildTree(result);
console.log(JSON.stringify(tree, null, 2));

这段代码首先创建了一个映射 (Map) 来存储每个节点的子节点，并确保不会出现循环引用。通过这种方式，可以构建出正确的树结构。

回到顶部