5/30 (월) 자료구조-3️⃣ 이진트리, BFS/DFS

 

 

 

 

 

❑ Binary Search Tree(이진 검색 트리)

 

 

모든 노드의 자식 노드가 단 두 개 뿐인 트리

오른쪽, 왼쪽 자식 두 개만 존재

왼쪽, 오른쪽 자식을 구분

한 쪽만 있거나 둘다 없는 노드가 있어도 됨

모든 왼쪽 자식의 값이 루트나 부모보다 작고, 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다

 

 

➤ 이진 트리 종류

 

이진 트리의 종류

 

완전 이진 트리(Complete binary tree)

• 마지막 레벨을 제외한 레벨은 노드를 빠짐없이 가득 채워야 한다
• 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 빠짐없이 채우되 반드시 끝까지 채울 필요는 없다
• 마지막 레벨의 왼쪽은 채워져 있어야 한다

 

정 이진 트리(Full binary tree)

• 각 노드가 0개 혹은 2개의 자식 노드를 가짐

 

포화 이진 트리(Perfect binary tree)

• 완전 이진 트리이면서 정 이진 트리인 이진 트리
• 모든 리프의 레벨이 같다
• 모든 레벨이 가득 차 있다

포화 이진 트리

 

 

 

 

❑ BFS/DFS

 

 

➤ 너비 우선 탐색(BFS, breadth-first search)

 

너비 우선 탐색

 

1. 낮은 레벨부터 왼쪽에서 오른쪽 방향으로 탐색하고

2. 한 레벨의 탐색이 끝나면 다음 레벨로 내려감

이 과정을 반복

 

 

➤ 깊이 우선 탐색(DFS, depth-first search)

 

깊이 우선 탐색

 

리프에 도달할 때까지 아래로 내려가면서 탐색

더 이상 탐색할 곳이 없으면 부모에게 돌아감

그런 다음 다시 자식 노드로 내려감

자식 노드가 2개 있을 때 부모 노드를 총 3번 거쳐가는데 언제 부모 노드의 값을 탐색할지는 3가지 방법이 있다.

예를 들어 D, H, I에서

전위 순회(preorder)는 부모 노드를 먼저 탐색한다.

D -> H -> I

중위 순회(inorder)는 부모 노드를 중간에 탐색한다.

H -> D -> I

후위 순회(postorder)는 부모 노드를 마지막에 탐색한다.

H -> I -> D

 

 

 

 

 

선배적 참견시점(선참시)

 

면접에서 반드시 물어보는 질문

어떤 어려움을 겪었고 어떻게 해결했는가!

자기가 블로그에 쓴 글에 대한 질문에 답변을 못하면 안된다

동기들과 함께 한다는 마음으로 응원도 많이 하고 소통 활발히 하자

선참시

좋은 리프레쉬 시간이었다.

 

 

 

그외) 배열 깊은 복사 쉽게하기

 

Arrays.clone() 메소드 이용

arr2 = arr.clone();

 

 

 

 

정리해놓고 포스팅을 늦게 올렸다.. ㅇ.ㅇ

점점 게을러 지고 있는데 정신 차릴 필요가 있다. 😡

 

 

읽어주셔서 감사합니다.

오개념에 대한 지적은 언제나 환영입니다.😍