• B 노드의 차수는 3이다.
• 노드의 깊이는 루트에서부터 센다.
• 부모, 자식, 형제 관계는 두 노드만 비교해서 판단한다.
• 어떤 노드의 자식이 다른 노드들의 부모 역할을 하면, 그 자식과 그 후손들을 묶어서 서브트리라고 한다.
• B 노드를 기준으로 보면 E는 서브트리가 아니다.

이진트리

<aside> 💡

트리 중에 각 노드가 최대 2개의 자식노드를 가질 때 이진트리(Binary Tree)라고 한다. (최대 Degree = 2) 같은 루트에 같은 자식노드가 하나 연결되어 있어도 자식노드의 위치가 왼쪽과 오른쪽으로 다르다면 서로 다른 트리이다.

</aside>

트리 순회

<aside> 💡

트리의 모든 노드를 방문하는 과정을 트리 순회(Tree Traversal)라고 한다.

</aside>

트리 순회 종류

전위 순회(Preorder) → 재귀함수 : 트리를 복사하거나, 전위 표기법을 구하는데 주로 사용됨

1. Root 노드를 방문
2. 왼쪽 서브 트리를 전위 순회
3. 오른쪽 서브 트리를 전위 순회

• 재귀함수

중위 순회(Inorder) → 정렬 : 이진 탐색트리(BST)에서 오름차순 혹은 내림차순으로 값을 가져올 때 주로 사용됨

1. 왼쪽 서브 트리를 중위 순회

2. Root 노드를 방문