Tree, BFS

1. 트리

1) 트리의 개념

- 비선형 구조

- 원소들 간에 1:N 관계를 가지는 자료구조

- 원소들 간에 계층관계를 가지는 계층형 자료구조

- 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조

 

2) 트리의 용어

- 노드 : 트리의 원소

- 루트 : 최상위 노드

- 형제 노드 : 같은 부모 노드의 자식 노드들

- 조상 노드 : 산선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

- 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

- 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들

- 노드의 차수 : 노드에 연결된 자식 노드의 수

- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값

- 단말 노드 : 차수가 0인 노드

- 노드의 높이 : 루트에서 노드에 이르는 간선의 수

- 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값

 

---

 

2. 이진 트리

1) 이진 트리의 개념

- 차수가 2인 트리

- 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리

- 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리

 

2) 이진 트리의 특성

- 높이가 i에서의 노드의 최대 개수는 2^i개

- 높이가 h인 이진 트리가 가질 수 있는 노듸의 최소 개수는 h+1 최대 개수는 2^h+1 - 1

 

3) 이진 트리의 종류

- 포화 이진 트리 : 높이가 h일때 최대의 노드 개수인 2^h+1 - 1의 노드를 가진 이진 트리

- 완전 이진 트리 : 높이가 h이고 노드 수가 n개 일 때 노드 번호 1번부터 n번까지 빈 자리가 없는 이진트리

- 편향 이진 트리 : 높이가 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가지는 트리

 

4) 배열 이진트리 표현

 

노드 번호가 i인 노드의 부모 노드 번호 : i / 2

노드 번호가 i인 노드의 왼쪽 자식 노드 번호 : 2 * i

노드 번호가 i인 노드의 오른쪽 자식 노드 번호 : 2 * i + 1

 

---

 

3. BFS

1) BFS란?

- 루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식

- 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 사용

	static void bfs(int[][] adjMatrix, int start) {
		int V = adjMatrix.length;
		
		//	1. 큐와 방문관리 배열 준비
		Queue<Integer> queue = new ArrayDeque<Integer>();
		boolean[] visited = new boolean[V];
	
		//	2. 시작 정점(정점 start) 큐에 넣고 방문 체크
		queue.offer(start);
		visited[start] = true;
		
		//	3. 큐로 방문관리
		while(!queue.isEmpty()) {
			int current = queue.poll();
			//	탐색 정점에 관련된 로직 처리
			System.out.println((char)(current + 65));
			for (int i = 0; i < V; i++) {
				if (adjMatrix[current][i] != 0 && !visited[i]) {
					queue.offer(i);
					visited[i] = true;
				}
			}
		}
	}

package com.algo.day7;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class CompleteBinaryTree<T> {

	private Object[] nodes;
	private final int SIZE;
	private int lastIndex; // 마지막으로 저장된 노드의 인덱스

	public CompleteBinaryTree(int size) {
		SIZE = size;
		nodes = new Object[size + 1];
	}

	public boolean isEmpty() {
		return lastIndex == 0;
	}

	public boolean isFull() {
		return lastIndex == SIZE;
	}

	public void add(T e) {
		if (isFull()) {
			System.out.println("포화상태입니다.");
			return;
		}
		nodes[++lastIndex] = e;
	}

	public void bfs() {
		if (isEmpty()) {
			return;
		}

		Queue<Integer> queue = new ArrayDeque<>();
		queue.offer(1); // 방문할 노드를 관리할 값 넣기

		while (!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println(nodes[current]);

			// 왼쪽 자식 노드
			if (current * 2 <= lastIndex)
				queue.offer(current * 2);
			// 오른쪽 자식 노드
			if (current * 2 + 1 <= lastIndex)
				queue.offer(current * 2 + 1);
		}
	}

	public void bfs2() {
		if (isEmpty()) {
			return;
		}

		Queue<Integer> queue = new ArrayDeque<>();
		queue.offer(1); // 방문할 노드를 관리할 값 넣기

		int level = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			System.out.print("level : " + level + " : ");
			for (int i = 0; i < size; i++) {
				int current = queue.poll();
				System.out.print(nodes[current] + "\t");

				// 왼쪽 자식 노드
				if (current * 2 <= lastIndex)
					queue.offer(current * 2);
				// 오른쪽 자식 노드
				if (current * 2 + 1 <= lastIndex)
					queue.offer(current * 2 + 1);
			}
			System.out.println();
			++level;
		}
	}

	public void bfs3() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] { 1, 0 }); // 방문할 노드를 관리할 값 넣기

		while (!queue.isEmpty()) {
			int[] data = queue.poll();
			int ind = data[0];
			int lev = data[1];
			System.out.println(nodes[ind] + "(" + lev + ")");

			if (ind * 2 <= lastIndex)
				queue.offer(new int[] { ind * 2, lev + 1 });
			// 오른쪽 자식 노드
			if (ind * 2 + 1 <= lastIndex)
				queue.offer(new int[] { ind * 2 + 1, lev + 1 });
		}
	}

	@Override
	public String toString() {
		return "CompleteBinaryTree [nodes=" + Arrays.toString(nodes) + ", SIZE=" + SIZE + ", lastIndex=" + lastIndex
				+ "]";
	}

}