[자료구조] 트리

강아지 이름은 봄이·2023년 6월 29일

1. 트리의 개념

배열이나 연결리스트, 스택, 큐처럼 일직선 데이터가 아니라 부모 자식 관계를 갖는 데이터들을 정리해둔 자료구조를 트리라고 한다.

2. 트리 VS 그래프

데이터가 선형인지 비선형인지에 따라 정리하는 자료구조가 다르다. 그 중에서 트리와 그래프는 비선형 자료를 정리할 때 사용하는 데이터 구조이다. 둘의 차이점은 순환 구조의 여부이다.

트리 구조는 순환 구조를 갖지 않는다.

3. 트리 구조의 명칭

Root node (부모 노드) : 부모가 없는 노드
Leaf node (단말 노드) : 자식이 없는 노드
edge (간선) : 노드와 노드를 연결하는 선
degree (차수) : 자식 노드의 개수
level (레벨) : root에서 어떤 노드까지의 edge의 수
depth (깊이) : root node ~ 현재 노드까지의 edge의 수
height (높이) : 현재 노드 ~ leaf node까지 가장 긴 edge의 수

4. 이진트리 (Binary Tree)

노드가 하나 이상의 자식을 가지면 트리 구조라고 말한다. 그 중에서 이진트리는 자식 노드의 개수가 2개이하인 트리를 말한다.

이진 트리의 유형

full binary tree (정이진트리) : 자식 노드의 개수가 0개 또는 2개인 트리
complete binary tree (완전 이진트리) : 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져있고, 마지막 레벨은 왼쪽 노드부터 채워져있는 트리
perfect binary tree (포화 이진트리) : 자식 노드의 개수가 2개이며, 모든 리프 노드가 동일한 레벨을 갖는 이진 트리

이진 탐색 트리 (Binary Search Tree)

공부중

5. 순회 방식

선형 자료 구조에서는 데이터에 순차적으로 접근하지만, 트리 구조에서는 다른 방식으로 데이터에 접근해야 한다.

트리구조에서 데이터(노드)를 방문하는 과정을 트리 순회라고 하며, 그 방법에는 전위 순회(preorder), 중위순회(inorder), 후위 순회(postorder) 세 가지가 있다.

그래프 순회 방식에는 크게 DFS와 BFS가 있는데, 트리구조에서 순회 방식은 DFS를 이용한다.

전위 순회 (preorder) : root node -> left -> right
중위 순회 (inorder) : left -> root node -> right
후위 순회 (postorder) : left -> right -> root node

전위 순회 (preorder)

이름에서도 알 수 있듯이 pre라는 뜻이 root node를 먼저 방문 처리 한 이후에 왼쪽 노드 -> 오른쪽 노드 순서로 탐색하겠다는 뜻이다.

전위 순회 코드 (python)

tree = ['A', 'B', 'C', 'D', 'E', 'F', None, 'G']
stack = [] #방문해야 하는 노드를 저장
def preorder(tree): #root -> left -> right
    stack = [0]
    res = [] #방문한 노드를 저장
    
    while stack:
        node = stack.pop()
        res.append(tree[node])
        
        node = node * 2 + 2 #오른쪽 노드
        if node < len(tree) and tree[node] != None:
            stack.append(node)
        node = node - 1 #왼쪽 노드
        if node < len(tree) and tree[node] != None:
            stack.append(node)
    return res

print(preorder(tree))