-1

我发现很少有与此相关的 SO 问题，但没有一个是基于我要解决的确切问题。

基本上，我正在研究一个树结构，每个节点都分配有一个 id。

目标是生成一个序列字符串，该字符串将提供一个路径来顺序遍历整个树。

例如下图的输出应该是123242523637321

在此处输入图像描述

如您所见，树从节点 1 开始，然后到达节点 2。

节点 2 连接到其他 3 个节点，即。节点 3、节点 4 和节点 5。

按照顺序，下一个节点是 3。

要转到下一个节点，即节点 4，我们必须回到节点 2，然后再转到节点 4，因此字符串变为12324

一旦我们得到最后一个节点，即节点 7，我们将返回第一个节点，因此字符串以子字符串7321结尾

我正在尝试构建一个逻辑，该逻辑将从给定的树结构生成字符串。

上图的示例树结构是 -

const sequenceObj = {
    1: {
        id: "Point_1cec2262-20f8-4985-adcb-b6d95a618d22",
        connectedNodes: ["2"]
    },
    2: {
        id: "Point_02bdae16-1cdb-48e1-a601-7b1e526eedb8",
        connectedNodes: ["1", "3", "4", "5"]
    },
    3: {
        id: "Point_55a68ac0-17ef-48a2-bf9f-c70004a27d99",
        connectedNodes: ["2", "6", "7"]
    },
    4: {
        id: "Point_8760427c-98bb-4e3e-85dd-59cba3b31c6f",
        connectedNodes: ["2"]
    },
    5: {
        id: "Point_79a7bcec-d110-43dc-b9ac-1552538bc1a5",
        connectedNodes: ["2"]
    },
    6: {
        id: "Point_37550cf0-4bd5-48b2-b32f-9018bd55c05f",
        connectedNodes: ["3"]
    },
    7: {
        id: "Point_2de67998-9e1f-4b06-af18-77d558d68254",
        connectedNodes: ["3"]
    }
};

如您所见，每个节点都有一个名为 connectedNodes 的属性，它可以帮助我们遍历树。

编辑 - 正如评论中指出的那样，属性connectedNodes（以前称为 children）存储连接节点的 id。提供的对象并不代表树，我们只需要使用这个对象从头到尾遍历，在这个例子中就是从id 1到7。

如果我遗漏了什么或需要更多信息，请告诉我。

谢谢！

4

2 回答 2

1

您的输入写在一个节点将其父节点列为children. 我们先解决这个问题 -

const node = (id, ...children) =>
  ({ constructor: node, id, children })

const tree =
  node(1, node(2, node(3, node(7), node(6)), node(4), node(5)))

现在我们可以写你的traverse-

function* traverse(t)
{ switch (t?.constructor)
  { case node:
      yield t.id
      for (const c of t.children)
      { yield *traverse(c)
        yield t.id
      }
  }
}

for (const v of traverse(tree))
  console.log(v)

1
2
3
7
3
6
3
2
4
2
5
2
1

或者我们可以将它们全部收集在一个字符串中

console.log(Array.from(traverse(tree)).join(""))

展开下面的代码片段以在您自己的浏览器中验证结果 -

const node = (id, ...children) =>
  ({ constructor: node, id, children })

function* traverse(t)
{ switch (t?.constructor)
  { case node:
      yield t.id
      for (const c of t.children)
      { yield *traverse(c)
        yield t.id
      }
  }
}

const tree =
  node(1, node(2, node(3, node(7), node(6)), node(4), node(5)))

console.log(Array.from(traverse(tree)).join(""))

1237363242521
于 2021-03-14T20:52:35.087 回答
0

您可以从子数组中取出已看到的节点并获取未看到键的节点。

const
    getSequence = (key, seen = {}) => {
        seen[key] = true;

        const unseen = sequenceObj[key]
                .children
                .filter(k => !seen[k]);

        return unseen.length
            ? `${key}${unseen.flatMap(k => getSequence(k, seen)).join(key)}${key}`
            : key;
    },
    sequenceObj = { 1: { id: "Point_1cec2262-20f8-4985-adcb-b6d95a618d22", children: ["2"] }, 2: { id: "Point_02bdae16-1cdb-48e1-a601-7b1e526eedb8", children: ["1", "3", "4", "5"] }, 3: { id: "Point_55a68ac0-17ef-48a2-bf9f-c70004a27d99", children: ["2", "6", "7"] }, 4: { id: "Point_8760427c-98bb-4e3e-85dd-59cba3b31c6f", children: ["2"] }, 5: { id: "Point_79a7bcec-d110-43dc-b9ac-1552538bc1a5", children: ["2"] }, 6: { id: "Point_37550cf0-4bd5-48b2-b32f-9018bd55c05f", children: ["3"] }, 7: { id: "Point_2de67998-9e1f-4b06-af18-77d558d68254", children: ["3"] } };

console.log(getSequence('1'));

于 2021-03-14T20:45:32.403 回答