이진 트리

이진 트리

이진 트리

모든 노드들이 2개의 서브트리를 갖는 트리

노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리

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

높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1)-1)개

 

 

1. 포화 이진 트리(Full Binary Tree)

모든 레벨에 노드가 포화상태로 차 있는 이진 트리

 

2. 완전 이진 트리(Complete binary Tree)

높이가 h이고 노드 수가 n개일 때(단, 2^h <= n < 2^(h+1)-1), Full 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

 

3. 편향 이진 트리(Skewed binary Tree)

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리

 

순회

트리의 각 노드를 중복되지 않게 전부 방문하는 것

1. 전위 순회(Preorder traversal)

VLR

자손노드보다 루트노드를 먼저 방문

A-B-D-E-H-I-C-F-G

def preorder_traverse(T) : # 전위순회
  if T :  # T is not None
    visit(T)  # print(T.item)
    preorder_traverse(T.left)
    preorder_traverse(T.right)

2. 중위 순회(Inorder traversal)

LVR

왼쪽 자손, 루트, 오른쪽 자순 순으로 방문

D-B-H-E-I-A-F-C-G

def inorder_traverse(T) : # 중위순회
  if T :  # T is not None
    inorder_traverse(T.left)
    visit(T)  # print(T.item)
    inorder_traverse(T.right)

3. 후위 순회(Postorder traversal)

LRV

루트노드보다 자손을 먼저 방문

D-H-I-E-B-F-G-C-A

def postorder_traverse(T) : # 후위순회
  if T :  # T is not None
    postorder_traverse(T.left)
    postorder_traverse(T.right)
    visit(T)  # print(T.item)

 

 

 

by SW expert academy