재귀함수 기초 문제들 해설 및 정리
이진트리 순회는 전위순회 , 중위순회 , 후위순휘 종류가 있습니다.
1번을 root 라고 표현
전위는 1 2 4 5 3 6 7 위에 부터 왼쪽 -> 오른쪽 순으로 탐색하고
중위는 4 2 5 1 6 3 7 왼쪽 -> 오른쪽 탐색
후위순회는 4 5 2 6 7 3 1 순으로 탐색
package TreeDFS;
import com.sun.tools.javac.Main;
// 1. Node 클래스를 만들어준다.
class Node{
// 2. data로 받을값과 좌우를 탐색하기 위한 lt , rt를 Node 클래스 형태로 선언
int data;
Node lt, rt;
public Node(int val){
data = val;
lt=rt=null;
}
}
public class TreeDFS {
// 3. Node 객체의 뿌리를 선언
Node root;
// 8. DFS 함수를 실행 시킴
public void DFS(Node root){
// 9. 마지막 노드까지 왔으면 null이기 때문에 종료
if(root == null){
return;
} else {
// 10. 다시 왼쪽의 루트를 호출해서 왼쪽부터 탐색하게 만들어 준다. 다시 DFS 호출 9번으로
// System.out.print를 찍는 위치에 따라 전위,중위,후위가 나뉘어짐
DFS(root.lt);
DFS(root.rt);
}
}
public static void main(String[] args) {
// 4. tree 형태의 객체를 생성
TreeDFS tree = new TreeDFS();
// 5. tree의 root에 1이라는 Node 타입 생성 [ 이러면 lt , rt 는 null인 상태 ]
tree.root = new Node(1);
// 6. tree의 root의 lt,rt 값에 Node 타입을 생성해서 넣어줌 [ 이러면 lt,rt 객체 형태의 2,3 을 data 값을 가지게 됨 ]
tree.root.lt = new Node(2);
tree.root.rt = new Node(3);
// 7. tree의 1번 노드 root노드 부터 시작
tree.DFS(tree.root);
}
}
System.out.print 위치는 직접 디버깅 해보면서 풀어보도록 하자!
'Algorithm' 카테고리의 다른 글
[프로그래머스] 삼총사 (0) | 2022.12.21 |
---|---|
[재귀함수] 재귀함수 기초 - 4 ( 부분집합 DFS ) (0) | 2022.12.12 |
[재귀함수] 재귀함수 기초 - 2 (0) | 2022.12.07 |
[재귀함수] 재귀함수 기초 - 1 (0) | 2022.12.07 |
[프로그래머스] 푸드 파이트 대회 (0) | 2022.11.29 |