Поддерево всех узлов в дереве с использованием DFS

Учитывая n узлов дерева и их соединения, выведите узлы Subtree каждого узла.

Поддерево узла определяется как дерево, которое является потомком узла. Название подчеркивает, что все, что является потомком узла дерева, также является деревом и является подмножеством большего дерева.

Примеры :

Ввод: N = 5
  0 1
  1 2
  0 3
  3 4
Выход: 
Поддерево узла 0 - 1 2 3 4 
Поддерево узла 1 равно 2 
Поддерево узла 3 равно 4

Ввод: N = 7
  0 1
  1 2
  2 3
  0 4
  4 5
  4 6
Выход:
Поддерево узла 0 - 1 2 3 4 5 6 
Поддерево узла 1 - 2 3 
Поддерево узла 4 равно 5 6 

Подход: выполните обход DFS для каждого узла и распечатайте все узлы, доступные с определенного узла.
Объяснение кода ниже:

1. Когда вызывается функция dfs (0, 0), start [0] = 0, dfs_order.push_back (0), loaded [0] = 1, чтобы отслеживать порядок dfs.
2. Теперь рассмотрим список смежности (adj [100001]), поскольку рассматриваемые элементы направленного пути, подключенные к узлу 0, будут в списке смежности, соответствующем узлу 0.
3. Теперь рекурсивно вызывайте функцию dfs, пока все элементы не пройдут через adj [0].
4. Теперь вызывается dfs (1, 2). Теперь start [1] = 1, dfs_order.push_back (1), visit [1] = 1 после обхода элементов adj [1].
5. Теперь выполняется обход adj [1], который содержит только узел 2, при обходе adj [2] он не содержит элементов, он прерывается и заканчивается [1] = 2.
6. Точно так же все узлы пройдены и сохраняют dfs_order в массиве, чтобы найти поддерево узлов.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.