트리 (tree)

: 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하며 자기 자신에게 돌아오는 순환이 없는 연결그래프이다.

트리와 관련된 용어

• 루트 노드(root node) : 부모가 없는 노드
• 단말 노드(leaf node) : 자식이 없는 노드
• 노드(node) : 트리를 구성하는 기본요소, 값과 하위노드를 가리키는 포인터를 가진다.
• 간선(edge) : 노드와 노드를 연결한 선
• 형제(sibling) : 같은 부모를 가지는 노드
• 노드의 크기(size) : 자신을 포함한 모든 자식 노드의 개수
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
• 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 높이(height) : 루트 노드에서 가장 깊은 노드까지의 길이

트리의 특징

• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  -> 간선은 항상 정점의 개수-1 개 만큼을 가진다

이진트리 (binary tree)

: 모든 노드가 두개 이하의 자식 노드를 가지는 트리

• 순회(traversal) : 트리에서 각 노드를 한번씩 체계적으로 방문하는 과정
  -> 부모노드, 왼쪽노드, 오른쪽노드를 어떤 순서로 방문하느냐에 따라 순회방법을 나눈다. 순회방법에 전위순회, 중위순회, 후위순회가 있다.

전위 순회 (preorder traversal)

: 현재노드 → 왼쪽노드 → 오른쪽노드

중위 순회 (inorder traversal)

: 왼쪽노드 → 현재노드 → 오른쪽노드

후위 순회 (postorder traversal)

: 왼쪽노드 → 오른쪽노드 → 현재노드

해시 테이블(hash table)

: