Algorithm_Tree

Tree(트리)

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

- 용어 정리

• 노드(node) : 트리의 원소
• 간선(edge) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
• 루트 노드(root node) : 트리의 시작 노드
• 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들
• 조상 노드 : 간선들 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리(subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들

나머지 노드들은 n개의 분리집합으로 분리될 수 있음.
T1,...,TN은 각각 하나의 트리가 되며 루트의 부트리(subtree)라고 한다.

• 차수(degree)
  노드의 차수 : 노드에 연결된 자식 노드의 수
  트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
  단말 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드
• 높이
  노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨

---

- 이진 트리

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

- 이진트리 특성

레벨 i에서의 노드 최대 개수 : $$2^i$$ 개
높이가 h인 이진 트리가 가질 수 있는 노드의 최소, 최대 개수 : h+1 ~ $2^{(h+1)}$ -1

 

- 포화 이진 트리(Full Binary Tree)

: 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
높이가 h일 때, 최대의 노드 개수인 $2^(h+1)$ -1 의 노드를 가진 이진 트리

 

- 완전 이진 트리(Complete Binary Tree)

: 높이가 h이고 노드 수가 n개 일때, 순서대로 1~n번까지 빈 자리가 없는 이진 트리

 

- 편향 이진 트리(Skewed Binary Tree)

: 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
(왼쪽, 오른쪽 편향 이진 트리)

 

- 순회(traversal)

: 트리의 노드들을 체계적으로 방문하는 것

 

1) 전위 순회(VLR)
: 부모노드 방문 후, 자식노드를 좌, 우 순서로 방문한다.

2) 중위 순회(LVR)
: 왼쪽 자식순회, 부모노드, 오른쪽 자식노드 순으로 방문한다.

3) 후위 순회(LRV)
: 자식노드를 좌우 순서로 방문한 후, 부모노드로 방문한다.

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

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

# 후위순회 알고리즘
def posorder_traverse(T): # 중위 순회
    if T:   # T is not None
        posorder_traverse(T.left)
        posorder_traverse(T.right)
        visit(T) # print(T.item)

---

이진트리의 표현

부모노드 인덱스를 n 이라고 하면, 자식노드 인덱스는 2n, 2n+1 이다.
자식노드의 인덱스가 N이라고 하면, 부모노드의 인텍스는 N//2 이다.
레벨 n의 노드 번호 시작 번호 : $2^n$

 

트리의 배열 생성 시, 공간 비효율에 대해 설명
간선의 개수, 노드끼리의 관계에 따른 배열(자식, 부모 번호를 서로 인덱스, 값으로 저장하는 예시)
: 어떠한 배열을 저장 시, 공간과 시간의 효율은 반비례 관계가 되는 경우가 있다.
예시는 시간의 효율을 위해 공간의 비효율을 감안하고 만드는 배열

• 배열을 이용한 이진 트리의 표현의 단점
  : 배열 원소에 대한 메모리 공간 낭비 발생
  파이썬이 아닌 다른 언어 경우, 배열의 크기 변경 어려워 비효율적

---

수식 트리

: 수식을 표현하는 이진 트리, 수식 이진 트리(Expression Binary Tree)라고도 한다.
연산자는 루트 노드이거나 가지 노드, 피연산자는 모두 잎 노드

 

---

# P.34 연습문제

def pre(root):
    if root:  # != 0:
        print(root, end=' ')
        pre(tree[root][0])
        pre(tree[root][1])


def pre1(root):
    print(root, end=' ')
    if tree[root][0] != 0:
        pre(tree[root][0])
    if tree[root][1] != 0:
        pre(tree[root][1])


inputS = '1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13'
lst = list(map(int, inputS.split()))
V = 13

# print(lst)
tree = [[0, 0] for _ in range(V + 1)]
parent = [0] * (V + 1)
# print(len(lst))
for idx in range(0, len(lst), 2):
    p, c = lst[idx], lst[idx + 1]
    if tree[p][0] == 0:
        tree[p][0] = c
    else:
        tree[p][1] = c
    parent[c] = [p]

print(tree)
print(parent)
pre(1)