Дълбочина срещу първа дълбочина Дървопреход в Javascript

Когато търсим през дърво, за да намерим дали съдържа определен възел, има два алгоритма, които можем да изградим. Можем да обиколим дървото с подхода първо на ширина или дълбочина.

Първият метод на дълбочина вярва, че ще стигнем колкото се може по-надолу по дървото, докато достигне задънена улица. След като достигне нулева стойност, тя започва да се архивира в горната част и следва същия процес.

Методът на първата широчина се опитва да стои възможно най-близо до върха. Той обикаля дървото един ред по един и разглежда всичките му възли. Продължава това, докато стигне до последния ред.

Изграждане на прост клас Node и Tree

Класът Node ще има конструктор с две свойства. Той ще има свойство за данни, за да съхранява стойността на възела и детско свойство, за да държи масив от дъщерни възли. Методът add () може да се използва за добавяне на нови възли към Дървото, а методът remove () ще изтрие нежелан дочерчен възел.

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

Вътре в класа Tree е мястото, където изграждаме нашите функции за търсене DFS и BFS за търсене чрез Дърво на възли.

Дълбочина-първи алгоритъм

За да проверим дали дървото съдържа определена стойност, използвайки подхода DFS, ще създадем функция, която започва от деклариране на масива за колекции, който ще съдържа коренния възел. След това ще изградим цикъл за време, който ще се изпълнява, докато вече няма стойност вътре в масива.

DFS използва стек, за да пресече дървото на възлите. Ще декларираме текущия възел, като изместим първата стойност на масива. С този възел ще проверим дали данните му са равни на стойността, която търсим. Ако е равно, ще върнем True и ще излезем извън функцията. Ако стойността на възела не съвпада, ще избутаме децата на този възел в предната част на масива, ако съществуват. Ние отместваме децата отпред, тъй като подходът DFS иска да стигнем до дъното на дървото, преди да проверим всеки елемент на братя. Ако след търсене на цялото дърво няма стойност, ние връщаме невярно в края на нашата функция.

Алгоритъм на ширината-първи

След изграждането на функцията DFS, функцията BFS ще изглежда много подобна, но с една малка разлика. Когато използваме BFS подхода, искаме да проверим всички елементи на братя, преди да преминем към следващия ред на дървото. Ще постигнем това с помощта на опашка. Опашката изисква от нас да използваме метода на натискане вместо метода на преместване, когато боравим с децата от възела. Вместо да вземем децата на възел и да ги настроим в предната част на масива от колекции, вместо това ще ги избутаме до края. Това гарантира, че ще проверим всички елементи на братя, преди да преминем към следващия ред на дървото.

Кога да използвам BFS срещу DFS?

И двата алгоритма могат да ви бъдат полезни при преминаване през дърво, за да търсите стойност, но кой е по-добър? Всичко зависи от структурата на дървото и какво търсите. Ако знаете, че търсената стойност е по-близо до върха, BFS подходът може да бъде по-добър избор, но ако дърво е много широко и не твърде дълбоко, DFS подходът може да бъде по-бърз и по-ефективен. Само имайте предвид, че има много други фактори, които ще трябва да определите, преди да изберете кой подход да предприемете. Имам увереност, че ще го разберете!