Форумна Поезия

[Chacho]

Рекурсивно обхождане на дърво в дълбочина

В класа Tree<Т> e реализиран и методът TraverseDFS(), който извиква частния метод PrintDFS(TreeNode<T> root, string spaces), който обхожда дървото в дълбочина и извежда на стандартния изход елементите му, така че нагледно да се изобрази дървовидната структура чрез отместване надясно (с добавяне на интервали).

Алгоритъмът за обхождане в дълбочина (Depth-First-Search или DFS) започва от даден връх и се стреми да се спусне колкото се може по-надолу в дървовидната йерархия. Когато стигне до връх, от който няма продължение се връща назад към предходния връх. Алгоритъма можем да опишем схематично по следния начин:

1. Обхождаме текущия връх.

2. Последователно обхождаме рекурсивно всяко едно от поддърветата на текущия връх (обръщаме се рекурсивно към същия метод последователно за всеки един от неговите преки наследници).
Създаване на дърво

За да създаваме по-лесно дървета сме дефинирали специален конструктор, който приема стойност на връх и списък от поддървета за този връх. Така позволяваме подаването на произволен брой аргументи от тип Tree<T> (поддървета). При създаването на дървото за нашия пример използваме точно този конструктор и той ни позволява да онагледим структурата му.