이진 트리 운행법 (Preorder, Inorder, Postorder)

▤ 목차

 

 

트리를 구성하는 각 노드를 찾아가는 방법이 있다.

✔ 트리 운행 방법

⌨ 이진 트리 운행

Root의 위치가 어디 있느냐에 따라 정해진다.

Root가 앞에 있으면 Preorder 운행법으로 진행(A > B >C)된다.

Root가 안에 있으면 Inorder 운행법으로 진행(B > A > C)된다.

Root가 뒤에 있으면 Postorder 운행법으로 진행(B > C > A)된다.

 

💻 이해하기

root를 기준으로 시작한다.

Root를 기준(A)으로 Left(왼쪽)으로 / Right(오른쪽)으로 뻗어나간다.

 

• Preorder 운행 (전위 순회)
  • ROOT -> LEFT -> RIGHT 순으로 운행한다. (시계 반대방향)
• Inorder 운행 (중위 순회)
  • LEFT -> ROOT -> RIGHT 순으로 운행한다.
• Postorder 운행(후위 순회)
  • LEFT -> RIGHT -> ROOT 순으로 운행한다.

 

 

---

 

 

 

✔ Preorder 운행법

 

 

 

💻 순서

중앙에서 시작해서 항상 왼쪽 먼저 진행된다.

 

A > B > D > C > E > G > H > F

 

👏 중요

ROOT -> LEFT -> RIGHT 순서

 

---

 

 

 

✔Inorder 운행법

 

 

💻 코드로 보기

D > B > A > G > E >  H > C >F

 

👏 중요

LEFT -> ROOT -> RIGHT 순서

---

 

 

✔Postorder

 

 

💻 코드로 보기

D > B > G > H > E > C > F > C > A

 

👏 중요

LEFT -> RIGHT -> ROOT 순서

---

 

 

😊정리

단말 노드 : 자식이 없는 노드, 디그리가 0인 노드

자식 노드 : 연결된 다음 레벨의 노드

부모 노드 : 어떤 노드에 연결된 이전 레벨의 노드들

형제 노드 : 동일한 부모를 갖는 노드들

트리 디그리 : 노드들의 디그리 중에서 가장 많은 수