[자료구조] 트리(Tree)

트리

트리란? 회사의 조직도, 가계도와 같이 나무처럼 뻗어나가는 모양의 사이클이 없는 그래프다.

www.designveloper.com

 

• 노드
• 간선
• 루트 노드: 트리의 맨 꼭대기
• 부모 노드/자식 노드
• 리프 노드: 자식이 없는 노드
• 차수와 깊이 그리고 높이
  • 차수: 특정 노드의 자식 수
  • 깊이: 특정노드로부터 루트노드와 떨어져있는 정도
  • 높이: max깊이 + 1

---

이진트리

트리의 자식을 2개로 한정하면, 이진트리

• 배열로 나타내기 좋다. 부모는 i, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1
• 만약 모든 자식이 꽉 차있지 않다면 배열도 같이 비워줘야한다.
• 이진트리는 한번 알면 여러모로 편하다.. 자식이 2개로 제한되어 있기 때문에 구현도 좋다… 그러니 확실하게 알아둘 것!

 

---

트리의 순회

트리를 탐색하는 순회 방법은 3 가지가 있다.

• 전위 순회(왼>뿌>오)
• 중위 순회(뿌>왼>오)
• 후위 순회(왼>오>뿌)

 

전위순회(preorder traverse)

 

'preorder'에 주목하자. 접미사 'pre'는 먼저, 이전에라는 뜻이 있다.

전위순회는 root를 preorder하라는 뜻이다. 즉 뿌리를 먼저 방문한다.

 

위와 같은 그래프가 있다고 하자. (트리는 그래프의 하위 개념이다.)

이 그래프를 preorder하면, 즉 앞에것 먼저 방문을 하면 0->1->3->7->8->4->9->10->2->5->11->6이다.

 

 

중위순회(inorder traverse)

중위순회는 뿌리노드의 자식들의 in에 방문하는 것이다.

뿌리노드가 자식들 중간에 방문되려면 먼저 왼쪽 자식들을 방문해주고 > 뿌리 노드를 데려오고 > 오른쪽 자식들을 방문해주면 된다. 결과는 7->3->8->1->9->4->10->0->11->5->2->6이다. 1과 2도 하위 자식들이 있으니 그 자식들의 중간에 넣어주기 위해 왼쪽 자식들 먼저 방문.. 뿌리 불러오기 오른쪽 자식들 방문. 이렇게 크고 작은 과정을 반복하면 된다.

 

 

후위순회(postorder traverse)

post의 뜻은 나중에, 이후에 라는 뜻이 있다. 즉 후위순회는 뿌리노드를 나중에 방문한다는 뜻이다.

결과는 7->8->3->9->10->4->1->11->5->6->2->0

---

구현

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

이 문제를 통해 트리 순회를 구현해보자.

[tree를 입력 받고 저장하는 방법]

import sys
N = int(sys.stdin.readline().strip())
tree = {}
 
for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]

파이썬 딕셔너리를 통해 왼쪽 자식과 오른쪽 자식을 딕셔너리의 [0][1]에 저장해준다.

def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right
 
 
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right
 
 
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root

각각의 순회 특성을 사용하여 print 해준다.