В жизни программирования мы всегда сталкиваемся с структурами деревьев. В последние несколько дней нам просто нужно управлять структурой дерева, поэтому мы записываем наши собственные методы и процессы работы. Теперь предположим, что есть такое дерево ((не имеет значения, является ли оно бинарным деревом или нет, принципы одинаковы)
1. Приоритет глубины
Английская аббревиатура - это DFS, а именно глубина первого поиска.
Поиск по глубине-это метод, который чаще используется на ранних стадиях развития. Его цель состоит в том, чтобы достичь листовых узлов поисковой структуры (то есть те HTML -файлов, которые не содержат гиперссылок). В HTML-файле, когда выбирается гиперссылка, связанный HTML-файл выполнит поиск по глубине, то есть отдельная цепочка должна быть выполнена полностью перед поиском оставшихся результатов гиперссылки. Поиск приоритета глубины следует гиперссылке в файле HTML до тех пор, пока он не может быть углублен, а затем возвращается в определенный HTML -файл и продолжает выбирать другие гиперссылки в файле HTML. Когда другие гиперссылки не доступны, поиск закончился. Процесс состоит в том, чтобы просто углубиться в каждый возможный ветвенную дорожку, пока он не может быть более глубоким, и каждый узел можно получить только один раз. Для приведенного выше примера результат первого прохождения глубины: A, B, D, E, I, C, F, G, H. (при условии, что левая сторона детского узла остается первой).
Приоритет глубины используется для прохождения каждого узла, и требуется структура данных, такую как куча. Характеристика стека - сначала перейти, а затем выйти. Весь процесс обхода выглядит следующим образом:
Во -первых, нажмите Узел А в кучу, стек (а);
Впрыскивание узел A и нажмите дочерние узлы A и B в кучу одновременно. В настоящее время B находится на вершине кучи, стека (B, C);
Впрыскивание узла B и нажимайте дочерние узлы B E и D в кучу. В настоящее время D находится на вершине кучи, стека (D, E, C);
Узел всплывающего аппарата D, дочерние узлы не нажимают, и E находится в верхней части кучи, стека (E, C);
Всплывающее узел E и нажмите дочерний узел E в стек (I, C);
... в свою очередь, и окончательный обход завершен. Код Java примерно следующим образом:
public void debinefirst () {Stack <map <string, object >> nodestack = new Stack <map <string, object >> (); map <string, object> node = new hashmap <string, object> (); nodestack.add (node); while (! nodestack.isempty ()) {node = nodestack.pop (); System.out.println (node); // Получить дочерний узел узла. Для двоичного дерева оно должно получить левый детский узел и правый детский узел списка узлов <map <string, object >> kids = getChildren (node); if (дети! = Null &&! Kids.isempty ()) {for (map Child: дети) {nodestack.push (Child);}}}} // Соглашения обезживают.2. Приоритет ширины
Английская аббревиатура - это BFS, что означает «широта первого исследования». В соответствии с тестированием процесса, доступ к каждому слою узлов доступен по очереди, и после доступа к одному слою каждый узел может получить доступ только к нему один раз. Для примера выше, результат прохождения ширины: A, A, B, C, D, E, F, G, H, I (при условии, что каждый слой узлов доступ к слева направо).
Приоритет ширины используется для прохождения каждого узла, и требуется структура данных, такую как очередь. Характеристика очереди-это первое, первое, и на самом деле, она также может использовать двойную очередь. Разница в том, что узлы могут быть вставлены и появляются в первой позиции двойной очереди. Весь процесс обхода выглядит следующим образом:
Сначала вставьте узел A в очередь, очередь (A);
Всплывающее узел A и вставьте дочерние узлы B и C в очередь. В настоящее время B находится в начале очереди, а C находится в конце очереди, очередь (B, C);
Всплывающий узел B и вставьте дочерние узлы D и E из B в очередь одновременно. В настоящее время C находится в начале очереди, а E находится в конце очереди, очередь (C, D, E);
Впрыскивание узла C и вставьте дочерние узлы F, G, h C of C в очередь. В настоящее время D находится в голове очереди, а H находится в конце очереди, очередь (D, E, F, G, H);
Узел D, D, D не имеет дочерних узлов, в настоящее время E находится во главе очереди, H находится в хвосте очереди, очередь (E, F, G, H);
... в свою очередь, и окончательный обход завершен. Код Java примерно следующим образом:
public void breadfirst () {deque > nodededeque = new Arraydeque > (); Карта узел = новый хэшмап (); nodedequ.add (узел); while (! nodedeque.isempty ()) {node = nodedequ.peekfirst (); System.out.println (Node); // Получить дочерний узел узла. Для двоичного дерева левый ребенок узел и правый дочерний узел узла должны получить список узла. > дети = getChildren (узел); if (дети! = null &&! Children.isempty ()) {for (map child: дети) {nodedequ.add (ребенок); }}}} // здесь используется двойная очередь, которая совпадает с использованием очереди Суммировать
Выше приведено все содержание этой статьи о примерах «Первая глубина» и «Ширин-первая» примеры кода реализации Java, и я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!