javascript - 如何在 JavaScript 中递归遍历通用树（不是 BST）？

Question

假设我们要对公司中存在的层次结构进行建模。最基本的数据结构称为employee. 每个employee都是它自己的对象/树，并且有两个属性：level一个是整数，reports一个是持有 0 或更多的对象/树employees。

我们可以说employee数据结构如下所示：

{
    employee: {
        level: Number,
        reports: Object //Contains 0 to N employees
    }
}

小型企业可以如下表示其组织：

{
boss: {
  level: 0,
  reports: {
    employee0: {
      level: 1,
      reports: {
        anotherEmployee0: {
          level: 2,
          reports: { /* ... */ },
        },
        anotherEmployee0: {
          level: 2,
          reports: { /* ... */ },
        },
      },
    },
    employee1: {
      level: 1,
      reports: { /* ... */ },
    },
  },
},
};

我们如何使用递归遍历这个结构？理想情况下，在没有语言功能抽象的情况下执行此操作，例如for ... in, foreach, map. 所以，“手动”。我很想看看这两种解决方案（有和没有所说的抽象），以进行比较。

标签： javascriptalgorithmrecursiondata-structurestree

Answer 1

for..in是一种核心语言结构，从一开始就是 JavaScript 语言的一部分。这是提供的第一种检查对象属性的方法。

我在这里提供两种解决方案。第一个将坚持您的数据结构，并将for..in用于读取给定对象的属性并对reports值执行条件递归。它调用用户提供的回调函数，因此用户可以决定如何处理迭代值。

第二个切换到更好的数据结构，因为更好的做法是不使用对象属性名称来表示动态内容。而是向您分配动态内容（“employee1”、“boss”等）的对象（可能是“名称”）添加一个属性。代替老式的回调系统，它将函数定义为生成器。

解决方案1（for..in+回调）：

这是 ES3 兼容的。

function traverse(org, callback, parent) {
    for (var name in org) {
        var obj = org[name];
        callback(name, obj.level, parent);
        if (obj.reports) {
            traverse(obj.reports, callback, name);
        }
    }
}

// demo with original data structure
var org = {boss: {level: 0,reports: {employee0: {level: 1,reports: {anotherEmployee0: {level: 2,reports: { /* ... */ },},anotherEmployee1: {level: 2,reports: { /* ... */ },},},},employee1: {level: 1,reports: { /* ... */ },},},},};

traverse(org, visit, null);

// Our function that processes the iterated values:
function visit(name, level, parent) {
    console.log("         ".slice(0, level) + name + " (level " + level + ") under " + (parent || "no one"));
}

解决方案2：（更好的数据结构+生成器）

这也使用解构、for..of循环、模板文字、、、repeat默认let参数值、...

function * iterate(org, parent=null) {
    for (let {name, level, reports} of org) {
        yield [name, level, parent];
        if (reports) {
            yield * iterate(reports, name);
        }
    }
}

let org2 = [{ 
    name: "boss", 
    level: 0, 
    reports: [{ 
        name: "employee0", 
        level: 1, 
        reports: [{ 
            name: "anotherEmployee0", 
            level: 2, 
            reports: [/* ... */]
        }, { 
            name: "anotherEmployee1", 
            level: 2, 
            reports: [/* ... */]
        }]
    }, {
        name: "employee1",
        level: 1,
        reports: [/* ... */]
    }]
}];

for (let [name, level, parent] of iterate(org2)) {
    console.log(`${" ".repeat(level)}${name} (level ${level}) under ${parent || "no one"}`);
}