尾递归JSON构造函数

Question

我有一个来自 NPM 包“directory-tree”的目录结构，我想将其展平为一个更简单的嵌套结构。我想要一个尾递归解决方案来将第一个对象转换为第二个对象，但我无法思考如何构造它。

当然首要条件是第一个结构中的'node'是'file'还是'directory'。如果它是一个文件，我们只需要文件的基本名称来键入相对路径。但是，如果它是一个目录，我们希望目录的基本名称成为对象的键并从那里递归。

我将使用他们的示例来说明结构：

{
  "path": "photos",
  "name": "photos",
  "size": 600,
  "type": "directory",
  "children": [
    {
      "path": "photos/summer",
      "name": "summer",
      "size": 400,
      "type": "directory",
      "children": [
        {
          "path": "photos/summer/june",
          "name": "june",
          "size": 400,
          "type": "directory",
          "children": [
            {
              "path": "photos/summer/june/windsurf.jpg",
              "name": "windsurf.jpg",
              "size": 400,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    },
    {
      "path": "photos/winter",
      "name": "winter",
      "size": 200,
      "type": "directory",
      "children": [
        {
          "path": "photos/winter/january",
          "name": "january",
          "size": 200,
          "type": "directory",
          "children": [
            {
              "path": "photos/winter/january/ski.png",
              "name": "ski.png",
              "size": 100,
              "type": "file",
              "extension": ".png"
            },
            {
              "path": "photos/winter/january/snowboard.jpg",
              "name": "snowboard.jpg",
              "size": 100,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    }
  ]
}

我希望最终结构更简单。类似于以下内容：

{
    "photos": {
        "summer": {
            "june": {
                "windsurf.jpg": "photos/summer/june/windsurf.jpg"
            }
        },
        "winter": {
            "january": {
                "ski.png": "photos/winter/january/ski.png",
                "snowboard.jpg": "photos/winter/january/snowboard.jpg"
            }
        }
    }
}

Answer 1

function copyNode(node, result = {}){
   if(node.type === "directory"){
      const folder = result[node.name] = {};
      for(const sub of node.children)
           copyNode(sub, folder);

  } else {
      result[node.name] = node.path;
  }
  return result;
}

这是一种简单的递归方法，这不是尾调用递归，因为只用一次尾调用遍历树非常困难（=不值得）。

Answer 2

您可以通过检查类型来采用递归方法。

对于 'directory' 取一个对象并迭代子对象。

否则将路径分配给具有给定名称的密钥。

function fn(source, target) {
    if (source.type === 'directory') {
        target[source.name] = {};
        (source.children || []).forEach(o => fn(o, target[source.name]));
    } else {
        target[source.name] = source.path;
    }
}

var source = { path: "photos", name: "photos", size: 600, type: "directory", children: [{ path: "photos/summer", name: "summer", size: 400, type: "directory", children: [{ path: "photos/summer/june", name: "june", size: 400, type: "directory", children: [{ path: "photos/summer/june/windsurf.jpg", name: "windsurf.jpg", size: 400, type: "file", extension: ".jpg" }] }] }, { path: "photos/winter", name: "winter", size: 200, type: "directory", children: [{ path: "photos/winter/january", name: "january", size: 200, type: "directory", children: [{ path: "photos/winter/january/ski.png", name: "ski.png", size: 100, type: "file", extension: ".png" }, { path: "photos/winter/january/snowboard.jpg", name: "snowboard.jpg", size: 100, type: "file", extension: ".jpg" }] }] }] },
    target = {};

fn(source, target);
    
console.log(target);

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

Answer 3

我们可以根据您的情况将深度优先搜索转换为尾递归。

let testObj = {
  "path": "photos",
  "name": "photos",
  "size": 600,
  "type": "directory",
  "children": [
    {
      "path": "photos/summer",
      "name": "summer",
      "size": 400,
      "type": "directory",
      "children": [
        {
          "path": "photos/summer/june",
          "name": "june",
          "size": 400,
          "type": "directory",
          "children": [
            {
              "path": "photos/summer/june/windsurf.jpg",
              "name": "windsurf.jpg",
              "size": 400,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    },
    {
      "path": "photos/winter",
      "name": "winter",
      "size": 200,
      "type": "directory",
      "children": [
        {
          "path": "photos/winter/january",
          "name": "january",
          "size": 200,
          "type": "directory",
          "children": [
            {
              "path": "photos/winter/january/ski.png",
              "name": "ski.png",
              "size": 100,
              "type": "file",
              "extension": ".png"
            },
            {
              "path": "photos/winter/january/snowboard.jpg",
              "name": "snowboard.jpg",
              "size": 100,
              "type": "file",
              "extension": ".jpg"
            }
          ]
        }
      ]
    }
  ]
};

function tailRecurse(stack, result){
  if (!stack.length)
    return result;
    
  // stack will contain
  // the next object to examine
  [obj, ref] = stack.pop();

  if (obj.type == 'file'){
    ref[obj.name] = obj.path;
      
  } else if (obj.type == 'directory'){
    ref[obj.name] = {};
    
    for (let child of obj.children)
      stack.push([child, ref[obj.name]]);
  }
  
  return tailRecurse(stack, result);
}


// Initialise
let _result = {};
let _stack = [[testObj, _result]];

console.log(tailRecurse(_stack, _result));

尾递归JSON构造函数

Tail recursive JSON constructor

javascript

json

node.js

recursion

tail-recursion