как заменить узел всеми его дочерними элементами в дереве

Question

Мне было интересно, как заменить узел недвоичного дерева его дочерними элементами. Например, я бы начал с такой структуры:

        a
     / / \ \
    b  c  d e
   /\  /    /\\
  f  g h    i jk

и в итоге получится, если я нацеливаю узел e на его дочерние элементы

          a
     / / \ \ \ \
    b  c  d i j k
   /\  / 
  f  g h    

в JSON, исходная структура будет выглядеть так:

{
  "id": "a",
  "children": [
    {
      "id": "b",
      "children": [
        {
          "id": "f",
          "children": []
        },
        {
          "id": "g",
          "children": []
        }
      ]
    },
    {
      "id": "c",
      "children": [
        {
          "id": "h",
          "children": []
        }
      ]
    },
    {
      "id": "d",
      "children": []
    },
    {
      "id": "e",
      "children": [
        {
          "id": "i",
          "children": []
        },
        {
          "id": "j",
          "children": []
        },
        {
          "id": "k",
          "children": []
        }
      ]
    }
  ]
}

Answer 1

Ваша проблема станет намного проще, если вы немного изменили структуру JSON. Для каждого узла сохраните родителя каждого узла и его непосредственных потомков.

Новая структура JSON

[
  {"id": "a", "parent": null, "children" : ["b", "c", "d", "e"] },
  {"id": "b", "parent": "a",  "children" : ["f", "g"]},
  {"id": "c", "parent": "a",  "children" : ["h"]},
  {"id": "d", "parent": "a",  "children" : []},
  {"id": "e", "parent": "a",  "children" : ["i", "j", "k"]}
]

Алгоритм

Допустим, ваш целевой узел e.

Теперь все, что вам нужно сделать, это изменить родителей ближайших детей e на a, поскольку a является родителем e. А затем удалите e.

Это сохранит структуру поддеревьев дочерних элементов e. Если вы не хотите этого, вы должны рекурсивно назначить a в качестве родителя для всех потомков e, а не только для ближайших.