트리와 전위,중위,후위 순회

트리(Tree)

• 1개 이상의 유한한 개수의 노드의 집합이다.
• 루트 노드와 0개 이상의 겹치치 않는 하위 나무 구조들의 집합으로 이루어 졌다.
  
• node : 위 그림에서는 a,b,c,d,e,f 이다.
• edge : 노드를 이어주는 선이다. (정보들간의 관계를 나타냄)
• path : edge에 의해 연결된 node들의 집합
• root node : 최상위 노드(위 그림에서는 A)
• parent(부모), children(자식), siblin(형제), grandparent(조부모), ancestor(조상) : 각 노드들의 관계
• leaf : 자식이 없는 노드
• subtree : 큰 트리에 속하는 작은 트리
• 차수 : 하위 subtree 개수

순회

• 전위 순위 (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