[Python] Tree1

• 트리의 개념
  • 비선형 구조
  • 원소들 간에 1:N 관계를 가지는 자료구조
  • 원소들 간에 계층관계를 가지는 계층형 자료구조
  • 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

 

• 정의
  • 노드(node) : 트리의 원소
  • 루트 노드(root node) : 트리의 시작 노드
  • 간선(edge) : 노드를 연결하는 선
  • 형제 노드(Sibling node) : 같은 부모 노드의 자식 노드들
  • 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
  • 서브 트리(subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
  • 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들
  • 차수(degree)
    • 노드의 차수 : 노드에 연결된 자식 노드의 수
    • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
    • 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드
  • 높이
    • 노드의 높이 : 루트에서 노드의 이르는 간선의 수, 노드의 레벨
      (루트 노드의 높이 0)
    • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

 

• 이진트리
  • 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
  • 자식 노드 최대 2개
    • 왼쪽 자식 노드(left child node)
    • 오른쪽 자식 노드(right child node)
  • 레벨 i에서의 노드 최대 개수 : 2^i
  • 높이가 h인 이진 트리가 가질 수 있는 노드의 개수 : h+1 ~ 2^(h+1) -1

<이진 트리>

• 포화 이진 트리(Full Binary Tree)
  • 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
  • 높이가 h일 때, 최대의 노드 개수인 2^(h+1)-1의 노드를 가진 이진 트리
  • 루트를 1번으로 하여 2^(h+1)-1까지 정해진 위치에 대한 노드 번호를 가짐

<포화 이진 트리>

• 완전 이진 트리(Complete Binary Tree)
  • 높이가 h이고 노드 수가 n개일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

<완전 이진 트리>

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

<편향 이진 트리>

---

• 이진 트리 순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것
  • 전위 순회(preorder traversal) : VLR(부모 -> 왼쪽 자식 -> 오른쪽 자식)
  • 중위 순회(inorder traversal) : LVR(왼쪽 자식 -> 부모 -> 오른쪽 자식)
  • 후위 순회(postorder traversal) : LRV(왼쪽 자식 -> 오른쪽 자식 -> 부모)

# edge 수
E = int(input()) # 4
arr = list(map(int, input().split())) # 1 2 1 3 3 4 3 5
V = E + 1 # 정점 수 == 1번부터 V번까지 정점이 있을때 마지막 정점 번호

# 부모번호를 인덱스로 자식번호 저장
ch1 = [0]*(V+1)
ch2 = [0]*(V+1)
for i in range(E):
    p,c = arr[i*2],arr[i*2+1] # 부모, 자식
    if ch1[p] == 0:
        ch1[p] = c
    else:
        ch2[p] = c

def pre_order(v):
    if v: # 0번 정점이 없으므로, 0번은 자식이 없는 경우를 표시
        print(v) # visit(v)
        pre_order(ch1[v])
        pre_order(ch2[v])

def in_order(v):
    if v:
        in_order(ch1[v])
        print(v)
        in_order(ch2[v])

def post_order(v):
    if v:
        post_order(ch1[v])
        post_order(ch2[v])
        print(v
        
pre_order(1) # 1 2 3 4 5
print('-------')
in_order(1) # 2 1 4 3 5
print('-------')
post_order(1) # 2 4 5 3 1