DFS (Depth First Search)

<aside> 💡 문제 1 : 아래 이진 트리에서 전위 순회 중위 순회 후위 순회하는 알고리즘을 작성하라

</aside>

Untitled

문제 해결 방안

  1. 먼저 상기 사진의 이진 트리를 구현한다
  2. 재귀 함수 호출을 통해 순회한다
import java.util.*;

//트리를 구성하는 각 노드의 클래스 이다
Class Node{
	int val; //노드의 데이터
	Node lt , rt; //이진 트리이므로 두개의 자식 노드 포인터가 존재한다
	
	//생성자부분이다 input_data가 인자로 들어오면 해당 인자의 데이터를 val 멤버 변수에 대입하여 생성
	//이후 자식 노드를 가리키는 포인터는 null로 지정한다 --> 리프노드
	Node(int input_data){
		val = input_data;
		lt = rt = null;
	}
}

Class Binary_Tree_DFS{
  Node root;
  
  //재귀 함수를 통해 루트 노드가 들어오면 순회하는 방식을 작성한다
  //출력부분이 앞에있으면 전위 중간이면 중위 끝이면 후위
	public void DFS(Node root)
	{
		if(root == null) return;
		else {
			System.out.print(root.val + " ");
			DFS(root.lt);
			DFS(root.rt);
		}
	}

	public static void main (String [] argv){
		Binary_Tree_DFS tree = new Binary_Tree_DFS();
		
		//사진처럼 이진트리를 만들어준다
	  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);
    
    System.out.print("순회 : ");
    tree.DFS(tree.root);
	}
}

<aside> 💡 문제2 : 자연수 N이 주어지면 1~N까지 원소로 이루어진 집합의 부분집합을 모두 출력하기

</aside>

문제 해결 방안