2022-01-21 Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 함.

 

 

 

전위 순회, 중위 순회, 후위 순회 예시

- 전위 순회(preorder traverse) : 뿌리를 먼저 방문. 뿌리->왼쪽 자식->오른쪽 자식 순 

 

0->1->3->7->8->4->9->10->2->5->11->6

 

- 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리를 방문, 왼쪽자식-> 뿌리-> 오른쪽 자식

 

7->3->8->1->9->4->10->0->11->5->2->6

 

- 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리를 방문, 왼쪽자식->오른쪽 자식-> 뿌리

 

7->8->3->9->10->4->1->11->5->6->2->0

 

- 층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문

 

 0->1->2->3->4->5->6->7->8->9->10->11

 

 

 

질문

• 이진 트리와 BST 이외에 어떠한 트리가 있을까요? 쓰레드 이진 트리, 힙 (공부안함)
• 균형 이진 탐색 트리란 무엇일까요?

균형이진 탐색 트리. 이진탐색크리는 한쪽으로 몰빵위험성이 있는데 균형 이진 탐색 트리는 높이를 제한시킴

• (Advanced) 힙이란 무엇일까요?

https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC