在 javascript 中使用 map 函数进行递归

Question

我有一张这样的地图，代表一个图形：

Map(5) {
  1 => [ 2, 3 ],
  2 => [ 7, 8, 10 ],
  3 => [ 4 ],
  10 => [ 12 ],
  4 => [ 11 ]
}

我有这个 class，它创建了一个有根树：

class RootedTree {
    constructor (data, ...descendants) {
      this.data = data;
      this.descendants = descendants;
    }
}

我的目标是：给定一个根，我想将该图转换为有根树。对于上面的示例，使用 1 作为根，我想要以下 return:

const RT = (...args) => new RootedTree(...args) // just to simplify 
// goal return:
RT(1, RT(2, RT(7), RT(8), RT(10, RT(12))), RT(3, RT(4, RT(11)), RT(5))

这是我的代码：

let local_descendants = []
const toRT  = (root, node_map) => {
    rt = new RootedTree(root)
    if (node_map.get(root) !== undefined){
        node_map.get(root).map((node) => toRT(node, node_map), local_descendants)
    } else {
        return null
    }

    return local_descendants
}

rt = new RootedTree(1, toRT(1, map))

我从 toRT 函数收到一个空数组。我想我可能搞砸了变量，但我不知道如何修复它。

Answer 1

在每次递归调用时，您可以 return 一个 RootedTree 的实例，将 root 参数作为 data，随后的递归调用作为 descendants:

var m = {1:[ 2, 3 ], 2:[ 7, 8, 10 ], 3:[ 4 ], 10:[ 12 ], 4:[ 11 ]}
class RootedTree {
   constructor (data, ...descendants) {
     this.data = data;
     this.descendants = descendants;
   }
   display(){
      return this.descendants.length === 0 ? `RT(${this.data})` : `RT(${this.data}, ${this.descendants.map(x => x.display()).join(', ')})`
   }
}
function toRT(root = 1){
   return (new RootedTree(root, ...(root in m ? m[root] : []).map(toRT)))
}
console.log(toRT().display())

输出：

RT(1, RT(2, RT(7), RT(8), RT(10, RT(12))), RT(3, RT(4, RT(11))))

Answer 2

@Ajax 的回答很好，但是您提到您有一个 Map，并希望该 Map 实例成为 toRT 的参数（好！）。

那么代码就是：

class RootedTree {
    constructor (data, ...descendants) {
        this.data = data;
        this.descendants = descendants;
    }
}

const toRT = (data, map) =>
    new RootedTree(data, ...map.get(data)?.map(child => toRT(child, map))??[]);

const map = new Map([[1,[2,3]],[2,[7,8,10]],[3,[4]],[10,[12]],[4,[11]]]);
const root = toRT(1, map);
console.log(root);

说明

从您的问题可以看出您对 Map 和 spread 语法很满意，所以让我们关注这个表达式：

map.get(data)?.map(child => toRT(child, map))??[]

optional chaining operator，即 ?.，将确保 .map() 仅在定义 map.get(data) 时调用。否则将使用 undefined 而不是 .map() 结果。

.map() 将迭代在 data 的 Map 条目中找到的子值，并通过调用 toRT(child, map) 转换它们中的每一个。后者将 return 一个 RootedTree 实例，因此 .map() 调用将 return 此类实例的数组，它们将作为我们节点的 descendants正在建设 data.

最后，Nullish coalescing operator，即 ??，会将 undefined 值（来自 map.get()）转换为空数组。这样，传播运算符在那种情况下也能正常工作。

因此首先创建更深的节点，为外部 new RootedTree 调用提供 descendants 参数。根节点是最后创建的。

在 javascript 中使用 map 函数进行递归

Recursion with map function in javascript

javascript

arrays

recursion

tree

graph-theory

说明