[Tree] 이진 트리, Binary Tree

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 이진 트리 (Binary Tree) 

• 각 노드의 자식 수가 2 이하인 트리
• 컴퓨터 분야에서 널리 활용되는 기본적인 자료구조
  • 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능케 하며 이진 트리의 서브트리를 다른 이진 트리의 서브트리와 교환하는 것이 쉽기 때문
• 이진 트리에 대한 용어는 일반적인 트리에 대한 용어와 동일
• 순환 정의
  • 이진 트리는 Empty 이거나, Empty가 아니면 루트 노드와 두 개의 이진트리인 왼쪽 서브트리와 오른쪽 서브트리로 구성된다.

 

- 특별한 형태의 이진 트리

• 포화 이진 트리 (Full binary tree) : 각 내부 노드가 두 개의 자식 노드를 가지는 트리
• 완전 이진 트리 (Complete binary tree) : 마지막 레벨을 제외한 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐 없이 채워진 트리 (포화 이진 트리는 완전 이진 트리임)

 

- 이진 트리의 속성

• 레벨 k에 있는 최대 노드 수 : 2^(k-1), k = 1, 2, 3 ...
• 높이가 h인 포화 이진 트리에 있는 노드 수 : 2^(h) - 1
• 높이가 h인 완전 이진 트리에 존재할 수 있는 최대 노드 수 : 2^(h-1) ~ 2(h) - 1
• n개의 노드를 가진 완전 이진 트리의 높이 : log(n+1)

 

- 파이썬 리스트에 저장된 이진 트리

• a[i]의 부모는 a[i//2]에 있다. 단, i > 1이다.
• a[i]의 왼쪽 자식은 a[2i]에 있다. 단 2i <= n이다.
• a[i]의 오른쪽 자식은 a[2i+1]에 있다. 단 2i + 1 <= n이다.

 

- 이진 트리의 순회

• 노드를 방문하는 순서에 따라 생각하면 됨
  • 중위 순회 (Inorder traversal) : 왼쪽 서브트리를 방문 후에 루트 노드를 방문 후 오른쪽 서브트리 방문 
  • 전위 순회 (Preorder traversal) : 루트 노드를 방문 후 왼쪽-오른쪽 서브트리를 순서대로 방문
  • 후위 순회 (Postorder traversal) : 왼쪽-오른쪽 서브트리를 순서대로 방문 후 루트 노드 방문
  • 층별 순회 (Leverorder traversal) : 맨 위 노드부터 시작하여 왼쪽-오른쪽 순서대로 차례로 내려가며 방문
  • 층별 순회를 제외하고 모두 스택 자료구조를 사용하여 연산함