-
DFS(Depth First Search) 깊이 우선탐색 위에서 아래로 탐색하는 것
최고 조상 : 루트 노드
데이터 하나, 주소두개를 저장하는 Node 클래스를 만든다.
부모(lt -> 자식 주소 / rt -> 자식주소)
어디서 부터 훑고 가느냐에 따라
- 전위순회 : 부모 > 왼쪽자식 > 오른쪽 자식 방향
- 중위순회 : 왼쪽 자식 > 부모 > 오른쪽 자식
- 후위순회 : 왼쪽 자식 > 오른쪽 자식 > 부모 (중요 병합정렬)
말단 노드엔 값이 없으므로 null이면 끝나게 한다.
아래는 재귀로 구현한 코드인데
스택에 쌓이면서 돌아간다.
class Node{ //이진트리 순회(깊이우선탐색) int data; Node lt, rt; //주소를 저장 public Node(int val) { data=val; lt=rt=null; } } public class Tree5 { Node root; //객체의 주소 저장(참조형) public void BFS(Node root){ if(root==null) return; else { System.out.print(root.data+" ");//전위순회 BFS(root.lt); //여기에서 출력하면 중위순회 BFS(root.rt); //여기에서 출력하면 후위순회 } } public static void main(String args[]) { Tree5 tree=new Tree5(); tree.root=new Node(1); tree.root.lt=new Node(2); tree.root.rt=new Node(3); tree.root.lt.lt=new Node(4); tree.root.lt.rt=new Node(5); tree.root.rt.lt=new Node(6); tree.root.rt.rt=new Node(7); tree.BFS(tree.root); } }
'자바알고리즘' 카테고리의 다른 글
[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 4장 기본 자료형 (0) 2022.11.18 자바 이진트리 순회(2.DFS - 넓이 우선탐색) (0) 2021.09.05 재귀함수와 스택프레임 (0) 2021.09.03 정렬정리(선택정렬, 버블정렬 , 삽입정렬) (0) 2021.09.02 TreeSet 알고리즘(중복제거 , 정렬가능) (0) 2021.08.22 댓글