[제주코딩베이스캠프] 눈떠보니 코딩테스트 전날 | 트리와 그래프

# 트리

- 나무를 거꾸로 뒤집어 놓은 모양으로 뿌리, 잎, 가지로 구성되어 있는 탐색을 위한 자료구조이다.
- None와 Edge를 이용해 데이터를 표현한다.

차수는 노드의 자식 노드 개수를 의미한다.

(1) 이진트리

: 자식노드가 최대 두개인 노드들로 구성된 트리로,
이진트리에는 포화이진트리와 완전이진트리 등이 있다.

- 포화이진트리

: 모든 노드가 두 개의 자식 노드를 가지고 모든 잎 노드가 동일한 깊이(레벨)을 갖는다.

- 완전이진트리

: 마지막 레벨을 제외한 나머지 노드들의 레벨이 완전히 채워져있고,
마지막레벨에서는 왼쪽부터 노드가 순서대로 채워져있다.

탐색을 위한 이진트리!
왼쪽 자식 노드는 나보다 작고, 오른쪽 자식은 나보다 크다는 특징이 있다.

---

* 이진트리의 순회 *

(1) 전위순회
: 루트 노드부터 잎 노드까지 아래 방향으로 방문
방문순서 : 자신 -> 왼쪽 -> 오른쪽

(2) 중위순회
: 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문
방문순서 : 왼쪽 ->. 자신 -> 오른쪽

(3) 후위순회
: 잎 노드를 방문 후 루트 노드를 순회한다.
방문순서 : 왼쪽 -> 오른쪽 -> 자신

---

* 이진트리 삽입 *

- 삽입하고자 하는 노드와 루트 노드 먼저 비교
- 루트 노드보다 작으면 왼쪽 루트로 이동,
반대로 크면 오른쪽 루트로 이동해서 해당 트리의 루트노드와 비교해서
자리를 찾아가는 과정이다.

 

---

# 그래프

그래프는 순환할 수 있다! (트리와 다른점)

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%A0%84%EB%82%A0/dashboard

눈떠보니 코딩 테스트 전날 - 인프런 | 강의

 

눈떠보니 코딩테스트 전날 강의 듣고 꼭 기억해야 하는 내용 정리

(이 게시글은 제주코딩베이스캠프 후원을 받아 제작되었습니다)