알고리즘 10 검색트리 | 트리와 이진트리 | JS

1. 트리 | Tree

• 계층적인 구조를 표현
  ex) 조직도, 디렉토리와 서브디렉토리 구조, 가계도
• 노드와 노드들을 연결하는 링크들로 구성
  * 링크(link) = 엣지(edge) = 브랜치(branch)
• 루트(root): 맨 위의 노드
• 부모-자식관계, 조상-자손 관계, 형제관계(부모가 동일한 노드)
• 리프(leaf) 노드: 자식이 없는 노드
• 레벨(level), 높이(height)
• 노드의 갯수가 N개인 트리는 항상 N-1개의 링크를 가짐
• 임의의 두 노드간의 경로는 유일함

2. 이진 트리 | Binary Tree

• 이진 트리에서 각 노드는 최대 2개의 자식을 가짐
• 각각이ㅡ 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자신인지가 지정됨(자식이 하나인 경우에도)

2-1. Full and Complete Binary Trees

• 정 이진트리 | Full Binary Tree
• 완전 이진트리 | Complete Binary Tree
  
• 높이가 h인 full binary tree는 2^h-1개의 노드를 가짐
• 노드가 N개인 full 혹은 complete 이진 트리의 높이는 O(logN)이다.
  (노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수도 있다.)

2-2. 이진트리의 표현

• 연결구조 표현 | Linked Structure 표현
  

2-3. 이진트리의 순회 | traversal

• 순회: 이진 트리의 모든 노드를 방문하는 일
• 중순회 순회 | inorder traversal
• 선순위 순회 | preorder traversal
• 후순위 순회 | postorder traversal
• 레벨오더 순회 | level-order traversal

2-3-1. 중순회 순회 | inorder traversal

• 좌 => root => 우

const result = []
function inorderTraversal(root) {
  if (root !== null) {
    inorderTraversal(root.left)
    result.push(root)
    inorderTraversal(root.right)
  }
}

2-3-2. 선순위 순회 | preorder traversal

• root => 좌 => 우

const result = []
function preorderTraversal(root) {
  if (root !== null) {
    result.push(root)
    preorderTraversal(root.left)
    preorderTraversal(root.right)
  }
}

2-3-3. 후순위 순회 | postorder traversal

• 좌 => 우 => root

const result = []
function postorderTraversal(root) {
  if (root !== null) {
    postorderTraversal(root.left)
    postorderTraversal(root.right)
    result.push(root)
  }
}

2-3-4. 레벨오더 순회 | level-order traversal

• 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로
• 큐(Queue)를 이용하여 구현

function levelorderTraversal(queue) {
  while(queue) {
    const current = queue.unshift()
    queue.push(current.left)
    queue.push(current.right)
    result.push(current)
  }
}

const queue = []
queue.push(root)
const result = []
levelorderTraversal(queue)

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠

---

Photo by Michael Dziedzic on Unsplash