이진트리(Binary tree) 순회방법

이진트리(Binary tree)란 자식노드가 최대 두 개인 노드들로 구성된 트리이다.
이진트리에는 full binary tree, complete binary tree, balanced binary tree 등이 있다.

바이너리 트리를 횡단하면서 트리의 모든 데이터를 가져오는 방법에는 세 가지 방법이 있다.

1. Inorder (Left, Root, Right)
2. Preorder (Root, Left, Right)
3. Postorder (Left, Right, Root)

1. Inorder (Left, Root, Right)
   루트 노드에서 시작해서 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭순회(symmetric traversal)라고도 합니다.
   

출력순서 : 4 - 2 - 5 - 1 - 3

2. Preorder (Root, Left, Right)
   루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이우선순회(depth-first traversal)라고도 합니다.
   

출력순서 : 1 - 2 - 4 - 5 - 3

3. Postorder (Left, Right, Root)
   루트 노드에서 시작해서 왼쪽 서브트리-오른쪽 서브트리-노드 순으로 순회하는 방식입니다.
   

출력순서 : 4 - 5 - 2 - 3 - 1