📚 Reference

• 참고 자료 1

📜 Chapter

DFS (Depth First Search)

‣

BST (Binary Search Tree)

Heap

Binary Tree

• Binary Tree
• 이진 트리
• 왼쪽 자식 - 부모 - 오른쪽 자식: 이진 트리의 기본 구조
• 트리가 복잡해서 규칙적으로 만들고자 binary tree를 만들게 되었다.
• 자식 노드의 개수는 무조건 2개만 한다.
• 부모 노드가 x이면 왼쪽 노드가 2x, 오른쪽 노드가 2x+1이다.

• 현재 노드 값/2 == 부모 노드 값
• 전위순회: 부모 - 왼쪽 - 오른쪽
• 중위순회: 왼쪽 - 부모 - 오른쪽
• 후위순회: 왼쪽 - 오른쪽 - 부모 → 병합 정렬에 사용한다.
• 일단 파고들어간다. 막히면 다시 뒤로 되돌아간다.