트리

트리 - 트리란?

• 사이클이 없는 그래프의 한 유형
  • 나무처럼 뿌리에서 가지로, 가지에서 잎으로 구성된 것을 바유하여 자료 간에 계층적 구조를 가질 때 이를 트리라고 칭함
  • 보통 루트를 위로해서 표현(뒤집어진 나무)
  • 
• 용어
  • 
  • 노드(Node)
    • 트리를 구성하는 꼭짓점
  • 루트(Root)
    • 트리인 그래프의 가장 높은 곳에 위치하는 시작 노드
  • 부모 노드(Parent Node)
    • 노드의 바로 한 단계 위에 있는 노드
  • 자식 노드(Child Node)
    • 노드의 바로 한 단계 아래에 있는 노드
  • 형제 노드(Sibling Node)
    • 부모가 같은 노드
  • 리프 노드(Leaf Node)
    • 자식이 없는 노드
    • 터미널 노드(Terminal Node)라고도 불린다
  • 레벨(Level)
    • 루트 노드를 레벨 0으로 시작하여, 자식 노드로 한 단계씩 내려갈 때마다 하나씩 증가하는 단계
  • 높이(Height)
    • 트리의 최대 높이
• Q. 물음에 답하시오
  • 
  • 노드의 총 개수는
  • 루트 노드는
  • E의 부모 노드는
  • E의 자식 노드는
  • H의 형제 노드는
  • 이 트리의 레벨은
  • 이 트리의 높이는

트리 - 트리의 종류

• 이진 트리(Binary Tree)
  • 트리의 차수가 최대 2인 트리를 칭함 (자식 노드를 최대 2개 가지는 트리)
  • 
• 완전 이진 트리(Complete Binary Tree)
  • 이진트리에서 마지막 레벨을 제외하면, 완전히 꽉 차 있고, 마지막 레벨은 연속되게 왼쪽부터 차있다면
  • 
• 포화 이진 트리(Full Binary Tree)
  • 모든 노드의 차수가 2차인 트리로, 리프 노드까지 모두 2개씩 채워진 경우
  • 
• Q. 2023 중등부 1차 1교시 - 10번 분수 트리

트리 - 순회

• 
  • 약어
    • L = Left
    • R = Right
    • N = Node (Current Node)
  • 중위 순회 (Inorder Traversal)
    • LNR
  • 전위 순회 (Preorder Traversal)
    • NLR
  • 후위 순회 (Postorder Traversal)
    • LRN
  • 레벨 순회 (BFS)