Sep.20.Wed.2023 Java 수업 18일차 이진트리 중위순회 / DFS와 BFS

• DFS, 깊이우선탐색 (Depth-First Search) -> 전위, 중위, 후위 순회
  그래프에서 깊이를 우선으로 탐색하는 알고리즘으로 시작 노드에서 출발하여 한 갈래로 끝까지 탐색한 후 다음 갈래로 이동한다.
  스택 또는 재귀함수를 사용하여 구현하며 더 이상 진행할 갈래가 없을 때 역추적하여 다른 갈래로 이동한다.
  깊이가 깊어질수록 스택에 저장되는 노드가 많아질 수 있으니 재귀의 최대 깊이에 주의해야 한다.

public class BinaryTree {
	TreeNode root;
	public BinaryTree() {
		this.root = null;
	}	
	
	// insert 메서드와 insertRec 메서드는 이진 트리에 새로운 노드를 삽입하는 데 사용된다.
	 	
	public void insert(int data) { // insert 외부에 노출되는 메서드
		root = insertRec(root, data);
	}
	
	private TreeNode insertRec(TreeNode root, int data) { // insertRec 실제 삽입 작업 메서드로 재귀적으로 노드를 삽입하고 적절한 위치를 찾아 새로운 노드를 생성한다.
		// 재귀적 : 자기 자신을 포함하고 다시 자기 자신을 사용해서 정의 내림
		if ( root == null ) {
			root = new TreeNode(data);
			return root;
		}
		if (data < root.data) {
			root.left = insertRec(root.left, data);
		} else if (data >  root.data) {
			root.right = insertRec(root.right, data);
		}
		return root;
	}
	
	public void inOrderT() { // in order traversal : 중위 순회
		inOrderTR(root);
	}	
    
	public void inOrderTR(TreeNode root) { // 중위 순회를 수행하여 트리의 노드를 출력하는 데 사용되고 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 노드 출력
		if (root != null) {
			inOrderTR(root.left);
			System.out.println(root.data + " ");
			inOrderTR(root.right);
		}
	}	
    
	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		tree.insert(50); // 루트
		tree.insert(30);
		tree.insert(70);
		tree.insert(20);
		tree.insert(40);
		tree.insert(60);
		tree.insert(80);
		tree.insert(90);
		
		System.out.println("이진 트리의 중위 순회 결과 : ");
		tree.inOrderT();
	}
}

이진트리 중위순회 출력 순서

 

• BFS, 너비우선탐색 (Breadth-First Search) -> 층별 순회
  그래프에서 너비를 우선으로 탐색하는 알고리즘으로 시작 노드에 인접한 모든 노드를 먼저 방문한 후 다음 레벨의 노드로 이동한다.
  큐(Queue)를 사용하여 구현하며 시작 노드를 큐에 넣고, 큐에서 노드를 하나씩 빼면서 인접한 노드를 큐에 추가한다.
  시작 노드에서부터 거리가 가까운 노드를 먼저 방문하기 때문에 최단 경로, 최소 연결성 검사 등을 찾을 때 유용하다.

import java.util.LinkedList;
import java.util.Queue;

 //Graph 클래스 : 자료 구조를 나타낸다.	

public class BFSGraph {
	private int V; // 그래프의 정점 수
	private LinkedList<Integer>[] adj; // 인접 리스트
	
	// 그래프 초기화
	// Graph 클래스의 생성자에서 그래프의 정점 수(V)를 받아서 초기화
	// adj 인접 리스트를 나타내고, 각 정점마다 인접한 정점들의 목록을 저장한다.
	public BFSGraph(int v) {
		this.V = v;
		adj = new LinkedList[v];
		for (int i = 0; i < v; ++i) {
			adj[i] = new LinkedList();
		}
	}
	
	// 그래프 간선 추가
	// addEdge 그래프에 간선을 추가하고, v와 w가 간선의 양 끝 정점을 나타낸다.
	public void addEdge(int v, int w) {
		adj[v].add(w);
	}
	
	// BFS 탐색을 수행
	public void BFS(int start) {
		
		// visited 배열은 각 정점의 방문 여부를 추적
		boolean[] visited = new boolean[V]; // 방문 여부를 표시하기 위한 배열
		
		// BFS를 위한 데이터 구조로 사용
		Queue<Integer> queue = new LinkedList<>();
		
		// 탐색은 시작 노드(start)에서 시작하고 시작 노드를 방문한 뒤 큐(queue)에 추가
		visited[start] = true;
		queue.add(start);
		
		// 큐가 비어질 때까지 반복적으로 다음 단계에 인접한 노드를 방문
		while(!queue.isEmpty()) {
			start = queue.poll();
			System.out.print(start + " ");		
			for(Integer neighbor : adj[start]) {
				if(!visited[neighbor]) {
					visited[neighbor] = true;
					queue.add(neighbor);
				}
			}
		}	
	}
}

import java.util.LinkedList;
import java.util.Queue;

// BFS main 메서드 :  그래프의 BFS 탐색을 구현하고, 주어진 시작 노드로부터 모든 연결된 노드를 너비 우선으로 탐색한다.

public class BFSMain {
	public static void main(String[] args) {
		// Graph 생성
		BFSGraph g = new BFSGraph(6);
		
		// 간선 추가
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(1, 3);
		g.addEdge(2, 4);
		g.addEdge(2, 5);
		
		System.out.println("탐색 결과 : ");
		
		// BFS를 시작 노드 0에서 호출해서 실행
		g.BFS(0);
		
		// 결과는 BFS의 탐색 결과인 노드 순서를 출력
	}
}