2021 #정보처리기사 필기요약 #2-1. 트리 순회방법, 차수 구하기

읽기전 참고사항

• 특정 노드를 언급하지 않고 트리의 차수를 구하는 경우 전체 트리에서 가장 큰 차수를 가지는 값을 구합니다.
• 노랑 마킹은 시험에 출제된 적이 있는 트리와 질문입니다.
• 회색 마킹은 트리 순회방법에 맞춰 제가 풀이한 결과입니다. 틀렸다고 생각되는 결과라면 댓글로 제보주세요.
  (확실하다고 생각되는 결과는 검정 글씨로 작성하였습니다.)

---

제 2과목 > 데이터 입출력 구현 > 자료구조 > 트리

---

루트 노드(Root Node)

트리에서 부모가 없는 최상위 노드이며, 트리의 시작점을 뜻한다.

 

트리 차수(Degree)

특정 노드에 연결된 자식의 수를 뜻한다.

 

트리 순회방법

구분	개념도	순회방법
전위 순회 (Pre-Order Traversal)		Root → Left → Right 루 좌 우
중위 순회 (In-Order Traversal)		Left → Root → Right 좌 루 우
후위 순회 (Post-Order Traversal)		Left → Right → Root 좌 우 루

---

트리 예시1

트리	구하고자 하는 정보	결과
	차수	2
	B의 차수	2
	전위 순회 (Preorder)	A-B-D-E-C-F-G
	중위 순회 (Inorder)	D-B-E-A-F-C-G
	후위 순회 (Postorder)	D-E-B-F-G-C-A

 

트리 예시2

트리	구하고자 하는 정보	결과
	차수	2
	B의 차수	2
	전위 순회 (Preorder)	A-B-D-G-E-H-C-F-I-J
	중위 순회 (Inorder)	G-D-B-H-E-A-C-I-F-J
	후위 순회 (Postorder)	G-D-H-E-B-I-J-F-C-A

 

트리 예시3

트리	구하고자 하는 정보	결과
	차수	2
	B의 차수	1
	전위 순회 (Preorder)	A-B-D-C-E-F
	중위 순회 (Inorder)	D-B-A-E-C-F
	후위 순회 (Postorder)	D-B-E-F-C-A

트리 예시4

트리	구하고자 하는 정보	결과
	차수	2
	B의 차수	1
	전위 순회 (Preorder)	A-B-D-C-E-G-H-F
	중위 순회 (Inorder)	D-B-A-G-E-H-C-F
	후위 순회 (Postorder)	D-B-G-H-E-F-C-A

 

트리 예시5

트리	구하고자 하는 정보	결과
	차수	3
	B의 차수	3
	전위 순회 (Preorder)	A-B-D-H-E-F-C-G
	중위 순회 (Inorder)	H-D-B-E-F-A-G-C
	후위 순회 (Postorder)	H-D-E-F-B-G-C-A

 

트리 예시6

트리	구하고자 하는 정보	결과
	차수	2
	B의 차수	0
	전위 순회 (Preorder)	+**/ABCDE
	중위 순회 (Inorder)	A/B*C*D+E
	후위 순회 (Postorder)	AB/C*D*E+

 

트리 예시7

트리	구하고자 하는 정보	결과
	차수	3
	B의 차수	3
	전위 순회 (Preorder)	A-B-D-E-F-H-I-C-G
	중위 순회 (Inorder)	D-B-E-H-F-I-A-C-G
	후위 순회 (Postorder)	D-E-H-I-F-B-G-C-A

 

!

틀린 결과 값이 있다면 제보 받습니다