트리 - 이진트리1

1. 이진트리

• 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
  • 왼쪽 자식 노드(left child node)
  • 오른쪽 자식 노드(right child node)

---

2. 이진트리의 특성

• 레벨 i에서의 노드의 최대 개수는 2ⁱ개

---

3. 포화 이진 트리

---

---

---

4. 이진트리의 순회(traversal)

• 순회(traversal)란 트리의 각 노드를 중복되지 않게 전부 방문(visit)하는 것을 ㅁ라하는데 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없습니다.
• 따라서 특별한 방법이 필요합니다.
• 순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것입니다.
• 3가지의 기본적인 순회 방법으로는
  • 전위 순회(preorder traversal) : VLR로 부모노드 방문 후, 자식노드를 좌, 우 순서로 방문합니다.
  • 중위 순회(inorder traversal) : LVR로 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문합니다.
  • 후위 순회(postorder traversal) : LRV로 자식노드를 좌우 순서로 방문한 후, 부모노드로 방문합니다.

---

---

---

---

5. 이진트리의 표현