Javascript - обход дерева для создания последовательности узлов

Question

Я нашел несколько вопросов SO, относящихся к этому, но ни один из них не был основан на конкретной проблеме, которую я пытаюсь решить.

По сути, я работаю над древовидной структурой, и каждому узлу присваивается идентификатор.

Цель состоит в том, чтобы сгенерировать строку последовательности, которая предоставит путь для последовательного обхода всего дерева.

В качестве примера вывод следующей диаграммы должен быть 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",
        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"]
    }
};

---

Как видите, каждый узел имеет свойство, называемое дочерними элементами, которое помогает нам перемещаться по дереву.

Сообщите мне, если я что-то пропустил или требуется дополнительная информация.

Спасибо!

Answer 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(""))

Разверните приведенный ниже фрагмент, чтобы проверить результаты в собственном браузере -

      1237363242521

Answer 2

Вы можете взять видимые узлы из дочернего массива и получить узлы невидимых ключей.