我想获取所有 parent 节点及其 child，对 javascript 中的给定数据使用 child id

Question

这是我的示例 object，假设如果我给 child id "services/bsf/diamSetting" 它应该 return 像这样的字符串 "nf-bsf -> bsfConfig -> services/bsf/diamSetting"

let arr = [{
  "attr": {
    "id": "nf-bsf",
    "name": "BSF",
    "sequence": 1
  },
  "children": [{
    "attr": {
      "id": "bsfGeneralConfig",
      "name": "General Configurations",
      "sequence": 10
    },
    "children": [{
      "attr": {
        "id": "services/bsf/bsfGlobalCfg",
        "name": "General Settings",
        "topic": "bsf.global.cfg",
        "sequence": 10
      }
    }, {
      "attr": {
        "id": "configurations/bsf/sbiErrorCodes",
        "name": "SBI Error Codes",
        "topic": "bsf.sbi.errorcodes",
        "sequence": 20
      }
    }]
  }, {
    "attr": {
      "id": "services/bsf/conLoggingLevel",
      "name": "Logging Level",
      "topic": "consistent.logging.cfg.topics",
      "sequence": 20
    }
  }, {
    "attr": {
      "id": "bsfServices",
      "name": "Service Configurations",
      "sequence": 30
    },
    "children": [{
      "attr": {
        "id": "services/bsf/managementService",
        "name": "Management Service",
        "topic": "bsf.managementservice",
        "sequence": 10
      }
    }]
  }, {
    "attr": {
      "id": "bsfConfig",
      "name": "Diameter Configurations",
      "sequence": 40
    },
    "children": [{
      "attr": {
        "id": "services/bsf/diamSetting",
        "name": "Settings",
        "topic": "common.diamsetting",
        "sequence": 10
      }
    }, {
      "attr": {
        "id": "configurations/bsf/diamPeerNode",
        "name": "Peer Nodes",
        "topic": "common.public.diampeernode",
        "sequence": 20
      }
    }, {
      "attr": {
        "id": "services/bsf/diamRoutingTable",
        "name": "Routing Table",
        "topic": "common.public.diamroutingtable",
        "sequence": 30
      }
    }, {
      "attr": {
        "id": "configurations/bsf/diamLoadShedding",
        "name": "Load Shedding Profiles",
        "topic": "common.public.diamloadshedding",
        "sequence": 40
      }
    }, {
      "attr": {
        "id": "configurations/bsf/diamMessagePriority",
        "name": "Message Priority Profiles",
        "topic": "common.public.diammessagepriority",
        "sequence": 50
      }
    }]
  }, {
    "attr": {
      "id": "bsf-sessionViewer",
      "name": "Session Viewer",
      "sequence": 50
    }
  }, {
    "attr": {
      "id": "administration",
      "name": "Administration",
      "sequence": 60
    },
    "children": [{
      "attr": {
        "id": "bsfBulkExportImport",
        "name": "Export & Import",
        "sequence": 10
      }
    }]
  }]
}];

我已经尝试过以下遍历，我要么得到未定义的路径，要么得到一些错误的路径。我什至没有得到 child 节点，这将以相反的顺序遍历。

var parent = [];
const findParent = (arr, id) => {
        for (let i=0; i<arr.length; i++) {
          if(arr[i].attr.id == id) {
            return parent;
          } else if (arr[i].children && arr[i].children.length) {
            parent.push(arr[i].attr.id);
            findParent(arr[i].children, id)
          }
        }
      };
let x = findParent(arr, "services/bsf/diamSetting");
console.log(x)

Answer 1

您的 parent 数组破坏了函数封装，造成了多个问题：

当一条路径被证明是一个不正确的路径时，它永远不会弹出，从而导致额外的数据。该数组跟踪所有访问过的节点，而不是到目标节点的特定路径。
该函数不是幂等的；多次调用后，parent 可能有来自先前遍历的陈旧信息。
如果这个全局数据名称改变，函数就会中断。函数应该能够承受超出其范围的重构。

这是解决这些问题的方法。我正在使用闭包来将结果数组限制在其函数的局部范围内，pop 撤消所有未最终导致目标的 push，并使用 some 退出找到目标后立即开始展开调用堆栈。

const tree = [ { "attr": { "id": "nf-bsf", "name": "BSF", "sequence": 1 }, "children": [ { "attr": { "id": "bsfGeneralConfig", "name": "General Configurations", "sequence": 10 }, "children": [ { "attr": { "id": "services/bsf/bsfGlobalCfg", "name": "General Settings", "topic" : "bsf.global.cfg", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/sbiErrorCodes", "name": "SBI Error Codes", "topic" : "bsf.sbi.errorcodes", "sequence": 20 } } ] }, { "attr": { "id": "services/bsf/conLoggingLevel", "name": "Logging Level", "topic": "consistent.logging.cfg.topics", "sequence": 20 } }, { "attr": { "id": "bsfServices", "name": "Service Configurations", "sequence": 30 }, "children": [ { "attr": { "id": "services/bsf/managementService", "name": "Management Service", "topic": "bsf.managementservice", "sequence": 10 } } ] }, { "attr": { "id": "bsfConfig", "name": "Diameter Configurations", "sequence": 40 }, "children": [ { "attr": { "id": "services/bsf/diamSetting", "name": "Settings", "topic": "common.diamsetting", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/diamPeerNode", "name": "Peer Nodes", "topic": "common.public.diampeernode", "sequence": 20 } }, { "attr": { "id": "services/bsf/diamRoutingTable", "name": "Routing Table", "topic": "common.public.diamroutingtable", "sequence": 30 } }, { "attr": { "id": "configurations/bsf/diamLoadShedding", "name": "Load Shedding Profiles", "topic": "common.public.diamloadshedding", "sequence": 40 } }, { "attr": { "id": "configurations/bsf/diamMessagePriority", "name": "Message Priority Profiles", "topic": "common.public.diammessagepriority", "sequence": 50 } } ] }, { "attr": { "id": "bsf-sessionViewer", "name": "Session Viewer", "sequence": 50 } }, { "attr": { "id": "administration", "name": "Administration", "sequence": 60 }, "children": [ { "attr": { "id": "bsfBulkExportImport", "name": "Export & Import", "sequence": 10 } } ] } ] } ];
 
const findPath = (children, targetId) => {
  const path = [];
  (function search(children) {
    return children?.some(child => {
      path.push(child.attr.id);
      
      if (child.attr.id === targetId || search(child.children)) {
        return true;
      }
      
      path.pop();
    });
  })(children);
  return path;
};

const path = findPath(tree, "services/bsf/diamSetting");
console.log(path.join(" -> "));

Answer 2

在函数外部使用 parent 变量会破坏递归，因为每个递归级别共享一个公共变量，这意味着一个递归的结果可能会覆盖另一个递归的先前结果。

您应该改为使 parent 变量成为 findParent 函数本身的私有变量，这样每次递归都会创建自己的数组并 modify/returns 它。

这里是修改后的代码，它使用第三个参数 hierarchy，其功能与您的 parent 相同，但对每个函数调用 (closure) 是私有的：

const arr = [ { "attr": { "id": "nf-bsf", "name": "BSF", "sequence": 1 }, "children": [ { "attr": { "id": "bsfGeneralConfig", "name": "General Configurations", "sequence": 10 }, "children": [ { "attr": { "id": "services/bsf/bsfGlobalCfg", "name": "General Settings", "topic" : "bsf.global.cfg", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/sbiErrorCodes", "name": "SBI Error Codes", "topic" : "bsf.sbi.errorcodes", "sequence": 20 } } ] }, { "attr": { "id": "services/bsf/conLoggingLevel", "name": "Logging Level", "topic": "consistent.logging.cfg.topics", "sequence": 20 } }, { "attr": { "id": "bsfServices", "name": "Service Configurations", "sequence": 30 }, "children": [ { "attr": { "id": "services/bsf/managementService", "name": "Management Service", "topic": "bsf.managementservice", "sequence": 10 } } ] }, { "attr": { "id": "bsfConfig", "name": "Diameter Configurations", "sequence": 40 }, "children": [ { "attr": { "id": "services/bsf/diamSetting", "name": "Settings", "topic": "common.diamsetting", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/diamPeerNode", "name": "Peer Nodes", "topic": "common.public.diampeernode", "sequence": 20 } }, { "attr": { "id": "services/bsf/diamRoutingTable", "name": "Routing Table", "topic": "common.public.diamroutingtable", "sequence": 30 } }, { "attr": { "id": "configurations/bsf/diamLoadShedding", "name": "Load Shedding Profiles", "topic": "common.public.diamloadshedding", "sequence": 40 } }, { "attr": { "id": "configurations/bsf/diamMessagePriority", "name": "Message Priority Profiles", "topic": "common.public.diammessagepriority", "sequence": 50 } } ] }, { "attr": { "id": "bsf-sessionViewer", "name": "Session Viewer", "sequence": 50 } }, { "attr": { "id": "administration", "name": "Administration", "sequence": 60 }, "children": [ { "attr": { "id": "bsfBulkExportImport", "name": "Export & Import", "sequence": 10 } } ] } ] } ];

const findParent = (
  arr,
  id,
  hierarchy = []  // Use an array here to store parents instead of using an external variable.
) => {
  for (let i = 0; i < arr.length; i++){
    // If id is found, push it to the result array, stop the loop, then return the result.
    if (arr[i].attr.id === id){
      hierarchy.push(arr[i].attr.id);
      return hierarchy;
    }
    
    // If id is not found, proceed to its children
    if (arr[i].children && arr[i].children.length){
      const childResult = findParent(
        arr[i].children,
        id,
        [...hierarchy, arr[i].attr.id]  // Pass the found parents so far to its child recursion.
      );
      
      // Only stop the loop and return the result if id is found in child.
      if (childResult){
        return childResult;
      }
    }
    
    // Proceed to the next loop if id is not found in current item AND its offspring children.
  }

  // Return null if id is not found in this branch.
  return null;
};

let x = findParent(arr, "services/bsf/diamSetting");

console.log(x && x.join(' -> '));

我想获取所有 parent 节点及其 child，对 javascript 中的给定数据使用 child id

I want to get all parent nodes along with its child, using a child id for a given data in javascript

javascript

recursion

parent-child

traversal