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

@Xsellizer · Регистрация: 23.02.2017

Студворк — интернет-сервис помощи студентам

Требуется написать функцию, которая принимает 2 аргумента:

исходное дерево
узел, от которого будет построено новое дерево.

Функция должна возвращать новое дерево с сохранёнными связями между узлами, в котором переданный узел является корневым.

Пример:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const tree = ['A', [ //     A
  ['B', [            //    / \
    ['D'],           //   B   C
  ]],                //  /   / \
  ['C', [            // D   E   F
    ['E'],
    ['F'],
  ]],
]];
 
transform(tree, 'B');
 
// ['B', [           //   B
//   ['D'],          //  / \
//   ['A', [         // D   A
//     ['C', [       //      \
//       ['E'],      //       C
//       ['F'],      //      / \
//     ]],           //     E   F
//   ]],
// ]];

Предполагаю, что стоит преобразовать дерево в список смежности, а далее из него уже собирать новое дерево (с новой вершиной). На данный момент нет идей, как это можно реализовать.

@mr_dramm · 30.08.2024, 10:22

Предположу что дерево не бинарное что может быть и такой вариант

A
/ | \
B C D

нужно ли разворачивать дерево новая вершина B?

Code
1
2
3
4
5
6
исходное   переносим      разворачиваем
A               B                   B
/                /                    /
F               A                    F
/                /                    /
B               F                    A

что выводить если нет искомой вершины?

вариант для перноса

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const tree = [
  "A",
  [
    ["B", [["D"]]],
    ["C", [["E"], ["F"]]],
  ],
];
 
const buildTree = (tree, target) => {
  let newTree = [tree[0], []];
  const traverse = (node, children) => {
    for (const dist of children ?? []) {
      let newNode = [dist[0], []];
      if (dist[0] == target) newNode = newTree = [dist[0], newTree];
      else node[1].push(newNode);
      traverse(newNode, dist[1]);
    }
  };
  traverse(newTree, tree[1]);
  return newTree;
};
 
console.dir(transform(tree, "B"), { depth: null });
 
[
  'B',
  [
    'A',
    [
      [ 'C', [ [ 'E', [] ], [ 'F', [] ] ] ]
    ],
    [ 'D', [] ]
  ]
]

@Xsellizer · 30.08.2024, 12:25 **[ТС]**

mr_dramm, спасибо за помощь! Разбираюсь пока что с вашим решением. Единственный момент: у вершин, у которых нет потомков, не должно быть пустого вложенного массива. Т. е. [ 'D'], а не ['D', []] - иначе тесты не пройдут. Пытаюсь переписать решение, чтобы оно удовлетворяло данному критерию.

P.S. вершина всегда существует в дереве.
'

Добавлено через 1 час 47 минут
Написал функцию для удаления пустых массивов во вложенном массиве:

JavaScript
1
2
3
4
5
6
7
8
  const removeEmptyArrays = (array) => {
    array.forEach((item) => {
      if (Array.isArray(item)) {
        _.remove(item, (el) => el.length === 0)
        removeEmptyArrays(item);
      }
    });
  };

Вот тесты:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import { sortTree } from '@hexlet/graphs';
import transform from '../transformer.js';
 
describe('transform', () => {
  describe('simple tree', () => {
    const tree = ['A', [
      ['B', [
        ['D'],
      ]],
      ['C', [
        ['E'],
        ['F'],
      ]],
    ]];
 
    it('#simple test1', () => {
      const expected = ['B', [
        ['A', [
          ['C', [
            ['E'],
            ['F'],
          ]],
        ]],
        ['D'],
      ]];
 
      const actual = transform(tree, 'B');
      expect(sortTree(actual)).toEqual(expected);
    });
  });
 
  describe('hard tree', () => {
    const tree = ['A', [
      ['B', [
        ['D', [
          ['H'],
        ]],
        ['E'],
      ]],
      ['C', [
        ['F', [
          ['I', [
            ['M'],
          ]],
          ['J', [
            ['N'],
            ['O'],
          ]],
        ]],
        ['G', [
          ['K'],
          ['L'],
        ]],
      ]],
    ]];
 
    it('#hard test 1', () => {
      const expected = ['F', [
        ['C', [
          ['A', [
            ['B', [
              ['D', [
                ['H'],
              ]],
              ['E'],
            ]],
          ]],
          ['G', [
            ['K'],
            ['L'],
          ]],
        ]],
        ['I', [
          ['M'],
        ]],
        ['J', [
          ['N'],
          ['O'],
        ]],
      ]];
 
      const actual = transform(tree, 'F');
      expect(sortTree(actual)).toEqual(expected);
    });
 
    it('#hard test 2', () => {
      const expected = ['I', [
        ['F', [
          ['C', [
            ['A', [
              ['B', [
                ['D', [
                  ['H'],
                ]],
                ['E'],
              ]],
            ]],
            ['G', [
              ['K'],
              ['L'],
            ]],
          ]],
          ['J', [
            ['N'],
            ['O'],
          ]],
        ]],
        ['M'],
      ]];
 
      const actual = transform(tree, 'I');
      expect(sortTree(actual)).toEqual(expected);
    });
  });
});

Все тесты падают, причем вывод тестов не очень информативен (пример):

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

белым цветом - то, что совпадает, зеленым, что ожидается, а красным - ошибки.

@mr_dramm · 30.08.2024, 17:30

Сообщение от Xsellizer

Написал функцию для удаления пустых массивов во вложенном массиве

не ищешь легкий путей =)

Сообщение от Xsellizer

Все тесты падают

потому что я сделал методом переноса, а нужно методом разворота(судя по предоставленным тестам), и кроме того в тестах выполняется еще функция sortTree(actual) над результатом функции transform

тут код на случай если сдашься сначала попробуй решить сам

Кликните здесь для просмотра всего текста

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const transform = (tree, target) => {
  let newTree = [tree[0]];
  let path = [newTree];
  const dfs = (node, children) => {
    if (!Array.isArray(children)) return;
    for (const dist of children) {
      let newNode = [dist[0]];
      if (dist[0] == target) {
        let prev = path.pop();
        const reverse = [prev];
        while (path.length) {
          revNode = path.pop();
          if (Array.isArray(revNode[1])) {
            revNode[1] = revNode[1].filter((e) => e !== prev);
          }
          prev[1] = [revNode];
          prev = revNode;
        }
 
        newNode = newTree = [dist[0], reverse];
      } else {
        if (!Array.isArray(node[1])) node[1] = [];
        node[1].push(newNode);
      }
      if (path.length) path.push(newNode);
      dfs(newNode, dist[1]);
      if (path.length) path.pop();
    }
  };
 
  dfs(newTree, tree[1]);
  if (path.length) path.pop();
  return newTree;
};

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

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

Решение