Javascript 树（对象数组）与祖先的遍历

Question

我正在尝试在 javascript 中创建一个树遍历函数。我还想要任何节点的祖先。这就是为什么我写了这样的代码：

const visit = (tree) => {
  if (!typeof ancestors){
    const ancestors = []
  }
  console.log(ancestors)
  if (Array.isArray(tree.children)) {
    ancestors.push(tree)
    tree.children.forEach((e) => {
      visit(e);
    })
  }
}

visit({
   "type":"root",
   "children":[
      {
         "type":"element",
         "children":[
            {
               "type":"element"
            },
            {
               "type":"element"
            },
            {
               "type":"element"
            },
            {
               "type":"element"
            }
         ]
      },
      {
         "type":"element"
      },
      {
         "type":"element"
      },
      {
         "type":"element"
      }
   ]
})

但它给我错误：

Error: ancestors is not defined

有人可以帮我做什么吗？ （我不想把这个

ancestors

作为对象的属性。）

Answer 1

因为ancestors是在这一行之后定义的，所以报错

if (!typeof ancestors){

在此行之前定义将解决问题

Answer 2

最短的解决方案是使

ancestors

具有默认值的参数并将

ancestors

传递给后续的递归调用：

const visit = (tree, ancestors = []) => {
  console.log(ancestors)
  if (Array.isArray(tree.children)) {
    ancestors.push(tree)
    tree.children.forEach((e) => {
      visit(e, ancestors);
    })
  }
}

如果您随后调用

visit(tree)

，祖先将被隐式初始化为

[]

。

替代方案是像 Konrad 的回答那样使用闭包，或者切换到完全迭代的实现，手动管理堆栈。

Answer 3

const

变量是块范围的

如果你不想拥有一个全局变量，你可以创建一个包装函数

const visit = (tree) => {
  const ancestors = []
  const req = (tree) => {
    if (Array.isArray(tree.children)) {
      ancestors.push(tree)
      tree.children.forEach((e) => {
        req(e);
      })
    }
  }
  
  req(tree)

  return ancestors
}

const result = visit({
  "type": "root",
  "children": [{
      "type": "element",
      "children": [{
          "type": "element"
        },
        {
          "type": "element"
        },
        {
          "type": "element"
        },
        {
          "type": "element"
        }
      ]
    },
    {
      "type": "element"
    },
    {
      "type": "element"
    },
    {
      "type": "element"
    }
  ]
})

console.log(result)