트리(tree)

트리의 정의

• 트리는 노드로 이루어진 비선형 자료구조

트리의 특징

• 하나의 루트 노드를 갖는다.
• 방향 그래프이다.
• 그래프의 한 종류이다. 최소 연결 트리라고도 불린다.
• 트리에는 사이클이 존재할 수 없다.(사이클이 존재한다면 트리가 아니고 “그래프”이다!)
• 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.

트리의 순회 방식

• 전위 순회(pre-order) 각 루트를 우선적, 순차적으로 방문하는 방식 1→2→4→8→9→5→10→11→3→6→13→7→14

• 중위 순회(in-order) 왼쪽의 하위 트리 우선 방문 후 → 루트 → 오른쪽 하위 트리 방문하는 방식 8→4→9→2→10→5→11→1→13→6→3→14→7

• 후위 순회(post-order) 왼쪽 하위 트리의 하위를 모두 방문 후 → 오른쪽 하위 트리의 하위를 우선 방문 후 → 루트를 방문하는 방식 8→9→4→10→11→5→2→13→6→14→7→3→1

• 레벨 순회(level-order) 계층에 존재하는 루트별로 방문하는 방식 1→2→3→4→5→6→7→8→9→10→11→12→13→14
  

트리의 종류

• 이진트리
  • 이진 탐색 트리
    • red-black tree
  • 포화 이진 트리
  • 완전 이진 트리
• 트라이(trie)