데이터 사이언스/알고리즘

트리 - 이진트리1

데이터분석가 이채은 2024. 6. 13. 09:00

1. 이진트리

  • 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
  • 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
    • 왼쪽 자식 노드(left child node)
    • 오른쪽 자식 노드(right child node)

2. 이진트리의 특성

  • 레벨 i에서의 노드의 최대 개수는 2i개

3. 포화 이진 트리

4. 이진트리의 순회(traversal)

  • 순회(traversal)란 트리의 각 노드를 중복되지 않게 전부 방문(visit)하는 것을 ㅁ라하는데 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없습니다.
  • 따라서 특별한 방법이 필요합니다.
  • 순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것입니다.
  • 3가지의 기본적인 순회 방법으로는
    • 전위 순회(preorder traversal) : VLR로 부모노드 방문 후, 자식노드를 좌, 우 순서로 방문합니다.
    • 중위 순회(inorder traversal) : LVR로 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문합니다.
    • 후위 순회(postorder traversal) : LRV로 자식노드를 좌우 순서로 방문한 후, 부모노드로 방문합니다.

5. 이진트리의 표현