[JAVA][알고리즘] DFS ( 이진 트리 순회 )

✅ 이진 트리 순회

• 이진 트리는 분할 정복 탐색 알고리즘으로 빠른 탐색이 가능하다는 장점이 있다.
• 탐색 방법에 따라 전위, 중위, 하위로 나눈다

 

 

전위

• Node를 기준으로 부모 -> 왼쪽 자식 -> 오른쪽 자식
• 자식이 여럿일 경우 끝까지 파고든다.
• 1 2 4 5 3 6 7

중위

• Node를 기준으로 왼쪽 자식 -> 부모 -> 오른쪽 자식
• 왼쪽 끝까지 도달하여 부모를 지나 오른쪽 방향으로 진행
• 4 2 5 1 6 3 7

후위

• 왼쪽 자식 -> 오른쪽 자식 -> 부모 방향
• 자식을 먼저 탐색 후 부모에게 간다.
• 4 5 2 6 7 3 1

 

>  코드 구현

구현된 코드를 기준으로, print문의 순서가 어디냐에 따라 

전위, 중위, 후위를 나눌 수 있다.

 

import java.util.*;

Class Node{
	int data;
    Node lt,rt;
    public Node(int val){
    	data=val;
        lt=rt=null;
    }
}

public class Main{
	Node root;
    public void DFS(Node root){
    	if(root==null) return; // 말단 노드는 값이 없음(null), 즉 말단 노드에 도착하면 종료
        else{
        	System.out.print(root.data+" "); // 전위순회
        	DFS(root.lt); // 트리에서 왼쪽으로 값을 전달
            // System.out.print(root.data+" "); 중위 순회
            DFS(root.rt); // 트리에서 오른쪽으로 값을 전달
            // System.out.print(root.data+" ");후위 순회
        }
    }
    public static void main(String args[]){
    	Main tree=new Main();
        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.rott.lt.rt=new Node(5);
        tree.root.rt.lt=new Node(6);
        tree.root.rt.rt=new Node(7);
    }
}

 

 

 

DFS로 부분집합 구하기

 

 

 

 

public class Solution {
    static int n;
    static int[] ch;
    public void DFS(int L){
        if(L==n+1){
            String tmp="";
            for(int i=1; i<=n; i++){
                if(ch[i]==1)
                    tmp+=(i+" ");
            }
            if(tmp.length()>0) System.out.println(tmp);
        }else{
            ch[L]=1;
            DFS(L+1);
            ch[L]=0;
            DFS(L+1);
        }
    }
    public static void main(String[] args) {
        Solution T=new Solution();
        n=3;
        ch=new int[n+1];
        T.DFS(1);
    }
}

 

 

 

 

 말단 노드까지의 가장 짧은 경로

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를
구하는 프로그램을 작성하세요.
각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를
길이로 하겠습니다.

가장 짧은 길이는 3번 노느까지의 길이인 1이다.

 

 

 

import java.util.*;
class Node{ 
    int data; 
    Node lt, rt; 
    public Node(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class Main{ 
    Node root; 
    public int DFS(int L, Node root){ 
        // 말단 노드
        if(root.lt==null && root.rt==null) return L;
        // 자식이 1개 밖에 없으면 에러 발생
        else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt));
    } 
  
    public static void main(String args[]) { 
        Main tree=new Main(); 
        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); 
        System.out.println(tree.DFS(0, tree.root)); 
    } 
}