이 기사에서는 Java에서 이진 트리를 구현하는 깊이 우선 순회 및 폭 최초의 순회 알고리즘에 대해 설명합니다. 다음과 같이 참조에 대해 공유하십시오.
1. 분석
이진 트리의 깊이 우선 순회의 비 수수성의 일반적인 관행은 스택을 채택하는 것입니다. 그리고 폭 최초의 횡단의 비 수수성에 대한 일반적인 관행은 대기열을 채택하는 것입니다.
깊이 우선 순회 : 가능한 각 가지 경로는 더 깊이 깊어 질 수 없을 때까지 침투 할 수 있으며 각 노드는 한 번만 액세스 할 수 있습니다. 이진 트리의 깊이 우선 순회는 매우 특별하며 선주문 트래버스, 중간 트래버스 및 후속 트래버스로 세분 될 수 있습니다. 특정 설명은 다음과 같습니다.
첫 번째 순서 Traversal : 모든 하위 트리의 경우 먼저 루트에 액세스 한 다음 왼쪽 하위 트리를 가로 지르고 마침내 오른쪽 하위 트리를 가로 지르십시오.
중간 주문 트래버스 : 모든 하위 트리의 경우 먼저 왼쪽 하위 트리를 가로지고 루트에 액세스 한 다음 결국 오른쪽 하위 트리를 가로 지르십시오.
순서 후 트래버스 : 모든 하위 트리의 경우 먼저 왼쪽 하위 트리를 가로지고 오른쪽 하위 트리를 가로 지르고 마침내 루트에 액세스하십시오.
너비 우선 트래버스 (Traversal) : 계층 구조라고도 알려져 있으며, 각 레이어에 상단에서 하단으로 액세스합니다. 각 레이어에서 왼쪽에서 오른쪽으로 (또는 오른쪽에서 왼쪽으로) 액세스 노드에 액세스하십시오. 하나의 레이어에 액세스 한 후에는 액세스 할 수있는 노드가 없을 때까지 다음 레이어로 들어갑니다.
2. 예를 들어
아래 그림에 표시된 이진 분류 트리는 선주문 트래버스 (재귀 적, 비수체 적), 내 주문형 트래버스 (재귀 적, 비 복구), 우편 주문형 (재귀 적, 비 복구) 및 폭이 먼저 트래버스를 사용해야합니다.
① 참조 코드
package binarytreetraversetest; import java.util.linkedlist; import java.util.queue;/** * 깊이 우선 순위 횡선 및 폭이 바이너리 트리의 넓은 우선 순위 이동 * @author fantasy * @version 1.0 2016/10/05 -2016/10/07 */public class binarytreetraversetest {public class void void main (string). 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 ( "선주문 트래버스 (재귀) :"); tree.preordertraverse (tree.getRoot ()); System.out.println (); System.out.print ( "인 주문 트래버스 (재귀) :"); 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 ( "순서 내 트래버스 (비 회수) :"); tree.inorderTraversEnoreCursion (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 ()); }}/*** 노드*/클래스 노드 <e는 비슷한 <e >> {e 값을 확장합니다. 노드 <e> 왼쪽; 노드 <e> 오른쪽; 노드 (e 값) {this.value = value; 왼쪽 = null; 오른쪽 = null; }}/** * 선례 시퀀스를 사용하여 바이너리 분류 트리 (이진 검색 트리라고도 함) */class binarysorttree <e 비슷한 <e >> {private node <e> root; binarySorttree () {root = null; } public void insertNode (e value) {if (root == null) {root = new Node <e> (값); 반품; } 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) preorderTraverse (node.right); } / ** * 바이너리 트리의 내에서 순서 (재귀) * @param node * / public void inorderTraverse (node <e> node) {if (node.left! = null) inorderTraverse (node.left); system.out.print (node.value + ""); if (node.right! = null) inorderTraverse (node.right); } / ** * 바이너리 트리의 우림 순서 (재귀) * @param node * / public void postordertraverse (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 preordertraversenorecursion (node <e> root) {linkedlist <node <e >> stack = new LinkedList <node <e >> (); 노드 <E> currentNode = null; stack.push (루트); 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 void inorderTraversenoreCursion (node <e> root) {linkedList <node <e >> stack = new LinkedList <node <e >> (); 노드 <E> currentNode = root; while (currentNode! = null ||! stack.isempty ()) {// 이진 분류 트리에서 가장 왼쪽 잎 노드 (currentNode는 null)에서 가장 왼쪽 잎 노드까지 (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.left; } currentNode = stack.pop (); System.out.print (currentNode.Value + ""); currentNode = currentNode.right; }} / ** * 바이너리 트리의 주문 후 순서 (비 재구성) * @param root * / public void postorderTraversenoreCursion (node <e> root) {linkedList <node <e >> stack = new LinkedList <node <e >> (); 노드 <E> currentNode = root; 노드 <E> 오른쪽 노드 = null; while (currentNode! = null ||! stack.isempty ()) {// 이진 분류 트리의 왼쪽 끝에있는 리프 노드 (currentNode는 null) {currentNode! = null) {stack.push (currentNode); currentNode = currentNode.left; } currentNode = stack.pop (); // 현재 노드에는 오른쪽 노드가 없거나 이전 노드 (출력 된 노드)는 현재 노드의 오른쪽 노드이며, 현재 노드는 출력 whink when when whine (currentNode.right || currentNode.right == RightNode) {system.out.print (currentNode.value + ""); RightNode = currentNode; if (stack.isempty ()) {return; // 루트 출력, Traversal Ends} currentNode = stack.pop (); } stack.push (currentNode); // currentNode = currentNode.right를 가로 지르지 않는 올바른 노드가 여전히 있습니다. }} / *** Hierarchical Traversal Binary Tree* @param node* / public void void void void void void void void void badthfirstraverse (queue <node <e >> queue = new LinkedList <node <e >> (); 노드 <E> currentNode = null; queue.offer (루트); 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 29 28 30 40 50 45 55
반면 트래버스 (재귀) : 15 16 20 28 29 30 35 40 45 50 55
우체류 횡단 (재귀) : 16 15 28 30 29 20 45 55 50 40 35
선주문 횡단 (비 수수료) : 35 20 15 16 29 28 30 40 50 45 55
반면 트래버스 (비 회복) : 15 16 20 28 29 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 Operation Dom Node Tips 요약", "Java 파일 및 디렉토리 작동 팁 요약"및 "Java Cache Operation Tips의 요약"을 볼 수 있습니다.
이 기사가 모든 사람의 Java 프로그래밍에 도움이되기를 바랍니다.