В этой статье описываются алгоритмы прохождения первой глубины и прохождения ширины, которые реализуют бинарное дерево в Java. Поделитесь этим для вашей ссылки, следующим образом:
1. Анализ
Обычная практика нерекурсивности первого прохождения глубины бинарных деревьев заключается в том, чтобы принять стек, а обычная практика нерекурсивности прохождения в ширине-принять очередь.
Первый обход глубины : каждый возможный путь ветвления может быть проникен до тех пор, пока он не может быть дальше, и каждый узел может быть доступен только один раз. Следует отметить, что пересечение глубины бинарного дерева является довольно особенной и может быть разделена на прохождение предварительного заказа, промежуточное обход и последующее обход. Конкретное описание заключается в следующем:
Первый порядок обход : для любого поддеревания сначала доступ к корню, затем пройдите его левый поддерек и, наконец, пройдите его правое поддерево.
Отслеживание среднего порядка : для любого поддеревания сначала пройдите его левый поддерек, затем получите доступ к корню и, наконец, пройдите его правое поддерево.
Отслеживание после порядка : для любого поддеревания сначала пересекайте его левый поддерек, затем пройдите его правый поддерек и, наконец, доступ к корне.
Широко-первая обход : также известная как иерархия, доступа к каждому слою сверху донизу по очереди. В каждом слое, узлы доступа слева направо (или справа налево). После доступа к одному слою вы войдете в следующий слой до тех пор, пока не будут доступны узлы.
2. Приведите примеры
Дерево бинарной сортировки, показанное на рисунке ниже, требует использования прохождения предварительного заказа (рекурсивного, нерекурсивного), пересечения порядка (рекурсивный, нерекурсивный), постмодерный обход (рекурсивный, нерекурсивный) и прохождение ширины.
① Справочный код
Пакет BinaryTraversetest; import java.util.linkedlist; import java.util.queue;/** * Приоритет глубины и приоритет приоритета двоичных деревьев * @author fantasy * @version 1.0 2016/10/05 - 2016/10/07 */public classtrestesteste. BinarySortTree <Integer> tree = new BinarySorttree <Integer> (); Tree.insertNode (35); Tree.insertNode (20); Tree.insertNode (15); Tree.insertNode (16); tree.insertnode (29); Tree.insertNode (28); Tree.insertNode (30); Tree.insertNode (40); Tree.insertNode (50); Tree.insertNode (45); Tree.insertNode (55); System.out.print («Предварительный заказ Traversal (рекурсивный):»); tree.preordertraverse (tree.getroot ()); System.out.println (); System.out.print ("Traversal In Order (рекурсивный):"); tree.inordertraverse (tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("Пост-опорное обход (рекурсивный):"); tree.postordertraverse (tree.getroot ()); System.out.println (); System.out.print ("ПРЕДВАРИЧЕСКИЙ ТРУБОР (НЕ-РЕКУРИВ):"); tree.preordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.print ("Traversal In Order (нерекурсивный):"); Tree.InOrderTaversenorEcursion (tree.getRoot ()); System.out.println (); System.out.println (); System.out.print ("Пост-заряд обход (нерекурсивный):"); tree.postordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.print («Проверка ширины:»); Tree.breadthfirsttraverse (tree.getroot ()); }}/*** Node*/class node <e Extends сопоставимо <e >> {e value; Узел <e> остался; Узел <e> правильно; Node (e value) {this.value = value; слева = null; справа = null; }}/** * Используйте прецедентную последовательность для создания двоичного дерева сортировки (также известного как двоичное дерево поиска) */class BinarySortTree <E Extens сопоставимо <e >> {private node <e> root; BinarySortTree () {root = null; } public void insertNode (e value) {if (root == null) {root = new Node <e> (value); возвращаться; } Node <e> currentNode = root; while (true) {if (value.compareto (currentnode.value)> 0) {if (currentNode.right == null) {currentNode.right = new Node <e> (value); перерыв; } currentNode = currentNode.right; } else {if (currentNode.left == null) {currentNode.left = new Node <e> (value); перерыв; } currentNode = currentNode.left; }}} public node <e> getRoot () {return root; } / ** * ПРЕДОСТАВЛЕНИЕ ПРЕДУПРЕЖДЕНИЕ ДВЕЙСТВИЯ Дерева (рекурсивное) * @param node * / public void preordertraverse (node <e> node) {System.out.print (node.value + ""); if (node.left! = null) preordertraverse (node.left); if (node.right! = null) предварительный заказ } / ** * Перенос бинарного дерева (рекурсивный) * @param node * / public inordertraverse (node <e> node) {if (node.left! = Null) inderdTraverse (node.left); System.out.print (node.value + ""); if (node.right! = null) inordertraverse (node.right); } / ** * Пост-порядка переселения двоичного дерева (рекурсивное) * @param node * / public void postertraverse (node <e> node) {if (node.left! = Null) postordertraverse (node.left); if (node.right! = null) postordertraverse (node.right); System.out.print (node.value + ""); } / ** * Преодоление предварительного заказа бинарного дерева (не-рекурсивного) * @param root * / public void предварительный заказ Узел <e> currentNode = null; stack.push (root); while (! Stack.isempty ()) {currentNode = Stack.pop (); System.out.print (currentNode.value + ""); if (currentNode.right! = null) stack.push (currentNode.right); if (currentnode.left! = null) stack.push (currentnode.left); }} / ** * Перенос бинарного дерева (не-рекурсивного) * @param root * / public inordertraversenorecursion (node <e> root) {linkedlist <node <e >> stach = new LinkedList <node <e >> (); Узел <e> currentNode = root; while (currentNode! = null ||! Stack.isempty ()) {// цикл до самого левого листового узла в двоичном дереве сортировки (CurrentNode не является null) while (currentNode! = null) {Stack.push (currentNode); currentNode = currentNode.left; } currentNode = Stack.pop (); System.out.print (currentNode.value + ""); currentNode = currentNode.right; }} / ** * Пост-порядка переселения двоичного дерева (нерекурсивное) * @param root * / public void postertraversenorecursion (node <e> root) {linkedlist <node <e >> стек = новый LinkedList <node <e >> (); Узел <e> currentNode = root; Узел <e> rightnode = null; while (currentNode! = null ||! Stack.isempty ()) {// цикл до тех пор, пока узел листья на самом левом конце двоичного дерева сортировки (CurrentNode не является null) while (currentNode! = null) {Stack.push (currentNode); currentNode = currentNode.left; } currentNode = Stack.pop (); // Текущий узел не имеет правого узла или предыдущего узла (узел, который был выводится) является правым узлом текущего узла, то текущий узел выводится, а (currentNode.right == null || currentNode.right == rightnode) {System.out.print (currentNode.value + ""); rightnode = currentNode; if (stack.isempty ()) {return; // корневые выходы, кончики обхода} currentNode = stack.pop (); } stack.push (currentNode); // все еще есть правильный узел, который не проходит Turnersnode = currentNode.right; }} / *** Бесполезное двоичное дерево, также известное как иерархическое двоичное дерево,* @param node* / public void farthfirsttraverse (узел <e> root) {queue <node <e >> queue = new LinkedList <node <e >> (); Узел <e> currentNode = null; queue.ffer (root); while (! queue.isempty ()) {currentNode = queue.poll (); System.out.print (currentNode.value + ""); if (currentNode.left! = null) queue.offer (currentNode.left); if (currentNode.right! = null) queue.offer (currentNode.right); }}}② Результат вывода
Перевернител предварительного заказа (рекурсивный): 35 20 15 16 28 28 30 40 50 45 55
Окончательный обход (рекурсия): 15 16 20 28 29 30 35 40 45 50 55
Поступором обход (рекурсия): 16 15 28 30 29 29 20 45 55 50 40 35
Перевернител предварительного заказа (нерекурсивное): 35 20 15 16 28 28 30 30 40 50 45 55
Триверс-порядок (нерекурсивный): 15 16 20 28 29 30 30 35 40 45 50 55
Поступором обход (не-рекурсивный): 16 15 28 30 29 20 45 55 50 40 35
Приоритет ширины: 35 20 40 15 29 50 16 28 30 45 55
Для получения дополнительной информации об алгоритмах Java, читатели, которые заинтересованы в этом сайте, могут просмотреть темы: «Учебное пособие по структуре данных Java и алгоритм», «Сводка операции Java Dom Node», «Сводка Java File и каталог
Я надеюсь, что эта статья будет полезна для всех Java Programming.