트리와 이진 트리

재귀가 가장 자연스럽게 맞아떨어지는 자료구조.

개념

트리는 가계도와 똑 닮았어요. 맨 위에 조상(루트)이 있고, 그 아래로 자식이 갈라지고, 자식이 또 자식을 가져요. 재미있는 건 자식 한 명을 콕 집어 봐도, 그 아래로 또 하나의 완전한 가계도가 펼쳐진다는 점이에요. 트리 어디를 잘라도 그 안이 다시 트리인 거죠. 그래서 트리는 재귀와 궁합이 딱 맞아요.트리는 노드마다 자식을 가지는 구조예요. 이진 트리는 자식이 최대 둘이고, 각각 left와 right로 불러요. 트리 문제가 재귀와 잘 맞는 이유는 명확해요 — 어떤 노드에서 봐도 왼쪽 서브트리와 오른쪽 서브트리가 다시 트리이기 때문이에요.그래서 트리 문제의 재귀는 거의 항상 같은 모양이에요. 빈 노드면 기본값을 돌려주고, 아니면 두 자식에게 같은 질문을 던진 뒤 그 답을 합쳐요.

네 가지 순회

순회	방문 순서	쓰임
전위 (preorder)	자기 → 왼쪽 → 오른쪽	트리 복사, 구조 출력
중위 (inorder)	왼쪽 → 자기 → 오른쪽	BST를 정렬된 순서로 얻기
후위 (postorder)	왼쪽 → 오른쪽 → 자기	자식 결과가 필요한 계산, 삭제
레벨 (level order)	위에서 아래로, 왼쪽에서 오른쪽	깊이별 처리, 큐 사용

앞의 셋은 코드가 완전히 같고 세 줄의 순서만 달라요. 레벨 순회만 재귀가 아니라 큐를 써요 — 사실상 BFS이고, 15주차에서 그래프로 확장돼요.'자기'를 언제 방문하느냐가 순회 이름을 가른다는 걸 작은 트리로 눈으로 확인해 볼게요. 아래 트리에서 세 순회의 방문 순서가 어떻게 갈리는지 따라가 봐요.

같은 트리, 세 순회의 방문 순서 차이
        1
       / \
      2   3
     / \
    4   5
preorder    :  1 2 4 5 3     self -> left -> right
inorder     :  4 2 5 1 3     left -> self -> right
postorder   :  4 5 2 3 1     left -> right -> self
self 를 언제 찍느냐가 전부예요:
  preorder  = 내려가기 직전
  inorder   = 왼쪽 마치고
  postorder = 두 자식 다 마치고

이진 탐색 트리

모든 노드에서 왼쪽 서브트리의 모든 값이 자기보다 작고, 오른쪽 서브트리의 모든 값이 자기보다 큰 트리를 이진 탐색 트리(BST)라고 해요. 이 성질 덕에 값을 찾을 때 매번 한쪽을 통째로 버릴 수 있어 평균 O(log n)이에요 — 11주차 이분 탐색과 같은 아이디어예요.

이 사이트에서 트리를 주고받는 방식

테스트 케이스는 JSON이어야 해서(같은 케이스가 JavaScript와 Python 채점기를 함께 돌아야 해요) 트리는 레벨 순서 배열로 적어요. null은 자식이 없다는 뜻이고, 뒤쪽 null은 생략해요. 채점기가 호출 직전에 이 배열을 노드로 바꿔서 넘겨주니까, 여러분은 root.left와 root.right만 쓰면 돼요.[3, 9, 20, null, null, 15, 7]은 루트 3에 자식 9와 20이 있고, 9는 자식이 없으며, 20의 자식이 15와 7인 트리예요. 새 노드가 필요하면 TreeNode를 두 언어 모두에서 바로 쓸 수 있어요.

패턴 코드

트리 재귀의 기본형빈 노드에서 기본값을 돌려주고, 두 자식의 답을 합쳐요.

javascript
Copy code
function depth(node) {
  if (node === null) return 0;
  return 1 + Math.max(depth(node.left), depth(node.right));
}

중위 순회세 줄의 순서만 바꾸면 전위·후위가 돼요.

javascript
Copy code
const out = [];
function walk(node) {
  if (node === null) return;
  walk(node.left);
  out.push(node.val);
  walk(node.right);
}

범위를 물려주며 BST 검사

javascript
Copy code
function check(node, low, high) {
  if (node === null) return true;
  if (low !== null && node.val <= low) return false;
  if (high !== null && node.val >= high) return false;
  return check(node.left, low, node.val) && check(node.right, node.val, high);
}

이번 주 문제

이번 주 진행0 / 4

주차 진행률

이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.

프로그래머스 진행률

길 찾기 게임 푼 문제로 표시
길 찾기 게임
Lv. 3풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.

중위 순회로 BST를 훑으면 왜 정렬된 순서가 나오는가?
BST 검사에서 부모만 보면 안 되는 반례를 하나 만들 수 있는가?
레벨 순회만 다른 셋과 구현이 다른 이유는?
루트 1, 왼쪽 2(왼 4·오 5), 오른쪽 3인 트리에서 전위·중위·후위 순서를 손으로 적을 수 있는가?

← 13주차 · 재귀와 분할 정복 15주차 · 그래프와 DFS · BFS →