[이산수학]이진트리의 순회(전위순회, 중위순회, 후위순회)

 

[이산수학]이진트리의 순회(전위순회, 중위순회, 후위순회)

 

모든 노드의 데이터를 처리할 수 있도록 한 번씩 방문하는 방법을 순회(Traversal)라고 합니다. 서브 트리에서 루트 노드(P)를 언제 방문하느냐에 따라 전위순회, 중위순회, 후위순회가 있습니다. 먼저 노드를 방문하는 순서를 확인하겠습니다. 

 

■ 노드를 방문하는 순서

1 항상 루트에서 시작합니다. 즉, 트리의 레벨 0에서 시작합니다. 

2 서브 트리에 대한 순회의 순서는 항상 왼쪽에서 오른쪽으로 이루어집니다. 

3 데이터를 읽기 전에 왼쪽, 혹은 오른쪽 노드가 있는지 확인하는 작업을 합니다. 

 

그럼 각 순회는 어떤 방식으로 이루어지는지 보겠습니다. 

 

■ 전위순회(Preorder Traversal)

루트 노드 - 왼쪽 노드 - 오른쪽 노드 순으로 방문하는 순회 방식

 

■ 중위순회(Inorder Traversal)

왼쪽 노드 - 루트 노드 - 오른쪽 노드 순으로 방문하는 순회 방식

 

■ 후위순회(Postorder Traversal)

왼쪽 노드 - 오른쪽 노드 - 루트 노드 순으로 방문하는 순회 방식

 

 

 

 

수학으로 이해하는 디지털 논리 이산수학 374p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------