Tree

트리

• 비선형 자료구조
• 원소들 간에 1:N 관계를 갖는다
• 원소들 간에 계층 관계를 갖는다
• 상위 윈소에서 하위 원소로 내려가면서 확장되는 트리 모양
  

이진 트리

• 모든 노드들이 2개 이내의 서브 트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대 2개 까지만 가질 수 있음 !

📍 이진트리의 종류

• 포화 이진 트리 (Full Binary Tree) : 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
• 완전 이진 트리 (Complete Binary Tree) : 포화 이진 트리의 노드 1번부터 n번까지 빈 자리가 없는 이진 트리
• 편향 이진 트리 (Skewed Binary Tree) : 한쪽 방향의 자식 노드만을 가진 이진 트리

📍 배열을 이용한 이진 트리의 표현

트리의 순회

• 트리의 순회에는 전위순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal) 이 있다.
  

• 전위 순회 : VLR - 부모 노드 방문 후, 자식 노드를 좌, 우 순서로 방문

• 중위 순회 : LVR - 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 방문

• 후위 순회 : LRV - 자식 노드를 좌, 우 순서로 방문 후 부모 노드로 방문

전위 순회 (VLR)

preorder_traverse(T):
  if T:
    visit(T)
    preorder_traverse(T.left)
    preorder_traverse(T.right)

중위 순회 (LVR)

inorder_traverse(T):
  if T:
    inorder_traverse(T.left)
    visit(T)
    inorder_traverse(T.right)

후위 순회 (LRV)

postorder_traverse(T):
  if T : 
    postorder_traverse(T.left)
    postorder_traverse(T.right)
    visit(T)

수식 트리의 순회