이진트리

정의

• 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리
  • 왼쪽 자식 노드 / 오른쪽 자식 노드
  • 두 자식 노드는 서로 완전히 다름

특성

• 레벨 i에서의 최대 노드 갯수: 2^i개
• 높이가 h인 이진 트리의 최소,최대 노드 수 : (h+1), (2^(h+1)-1)

종류

• 포화 이진트리
• 완전 이진트리
  • 노드의 수가 n개일 때, 노드 1~n까지 빈자리가 없는 이진트리
• 편향 이진트리
  • 높이 h에 대한 최소 갯우의 노드를 가진 트리
  • 한쪽 방향의 자식 노드만 가진 이진트리

이진트리의 종류

순회

특징

• 각 노드를 중복 없이 방문
• 비선형 구조이기 때문에 선후 연결관계를 알 수 없음

방법

전위순회 (VLR)

def preorder(T):
	if T:
    	visit(T.data)
        preorder(T.left)
        preorder(T.right)

중위순회 (LVR)

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

후위순회 (LRV)

def postorder(T):
    if T:
        postorder(T.left)
        postorder(T.right)
        visit(T.data)

 

표현

배열을 이용

• 노드번호가 i인 노드의 부모 번호: i // 2
• 노드번호가 i인 노드의 왼쪽 자식 노드 번호: 2 * i
• 노드번호가 i인 노드의 오른쪽 자식 노드 번호: 2 * i + 1
• 레벨 n에서의 시작 노드 번호: 2^n