[10일차 과제] 자료구조(트리)

[10일차 과제] 자료구조(트리)

2026. 6. 3. 22:03ㆍKDT/과제

1. 트리란?

트리의 정의
트리를 사용하는 이유
트리 종류
배열과의 차이점

2. 트리의 주요 용어 정리 (with 그림)

3. 트리 순회 방식

전위 순회(Preorder)
중위 순회(Inorder)
후위 순회(Postorder)

4. 파이썬으로 간단한 트리 구현

Node 클래스
트리 연결
데이터 출력

1. 트리(Tree)란?

1. 트리의 정의

계층적인 자료를 표현하는데 적합한 비선형 자료구조
ex. 계층적 데이터 저장, heap, 데이터베이스 인덱싱, Trie
구성 : 노드(node)와 간선(edge, branch)
노드들이 나무 가지처럼 연결되어 있음 (나무를 거꾸로 뒤집어 놓은 모양과 유사)
트리 내에 다른 하위 트리가 존재하는 구조가 반복되어 재귀적 자료구조이기도 함
노드가 N개인 트리는 N-1개의 간선을 가짐

2. 트리를 사용하는 이유

계층적 데이터 표현
빠른 탐색 속도를 가지고 있어 검색 연산을 많이 할 때 주로 사용
대용량 데이터 관리

3. 트리 종류

# 편향 트리 (Skew Tree) : 모든 노드들이 자식을 하나만 가진 트리

# 이진 트리 (Binary Tree) : 각 노드의 차수(자식 노드)가 2 이하인 트리

# 완전 이진 트리 (Complete Binary Tree) : 루트 노드를 뺀 나머지 노드의 차수가 2인 트리

# 이진 탐색 트리 (BST : Binary Search Tree) : 순서화된 이진 트리. 왼쪽 자식은 부모 값보다 작은 값을 가지고, 오른쪽 자식은 부모의 값보다 큰 값을 가짐

# m원 탐색 트리 (m-wat Search Tree) : 최대 m개의 서브 트리를 갖는 탐색 트리. 이진 탐색트리를 확장한 형태 (높이를 줄임)

# 균형 트리 (B-Tree : Balanced Tree) : m원 탐색 트리에서 높이 균형을 유지하는 트리

4. 배열과의 차이점

배열 :
- 데이터가 일렬로 나열된 선형 구조
- 인덱스를 통한 접근
- 연속적 메모리 공간에 할당
- 빠른 조회
트리 :
- 데이터들의 계층적 관계를 나타내는 비선형 구조
- 루트부터 타고 내려가는 탐색
- 흩어진 메모리 공간에 노드 단위로 할당 및 참조로 연결
- 폴더 구조, 조직도

2. 트리의 주요 용어 정리 (with 그림)

Node : 트리를 구성하고 있는 기본 요소. 키 또는 값과 하위 노드에 대한 포인터를 가짐 (A~J)
Edge : 노드와 노드 간의 연결선
Root Node : 트리 구조에서 부모가 없는 최상위 노드 (A)
Parent Node :자식 노드를 가진 노드 (B,C,D의 부모 노드는 A)
Child Node : 부모 노드의 하위 노드 (B의 자식 노드는 E, F, G)
Sibling Node : 같은 부모를 가지는 노드 (I, J는 형제 노드)
Leaf Node : 자식 노드가 없는 노드. external node, outer node (외부노드), terminal node (단말노드) 라고도 함
(E, F, G, H, I, J)
Depth(깊이) : 루트에서 어떤 노드 까지의 간선(edge) 수 (루트 노드(A)의 깊이 : 0, D의 깊이 : 1)
Level(레벨) : 루트에서 어떤 노드까지의 간선(edge) 수 (H의 레벨 : 3)
Degree(차수) : 노드의 자식 수 (leaf node의 차수 : 0, B의 차수 : 3)

3. 트리 순회 방식

L : 왼쪽 서브 트리, root : 루트, R : 오른쪽 서브트리
L, R은 고정되어 있고 R의 위치에 따라 종류가 3종류

1. 전위 순회(Preorder) : root -> L -> R

2. 중위 순회(Inorder) : L -> root -> R

3. 후위 순회(Postorder) : L -> R -> root

4. 파이썬으로 간단한 트리 구현

자식 노드가 2개만 있는 이진 트리 구현이 더 간단하기 때문에 이진트리 구현을 먼저 해보자

1. class BinarytreeNode 구현

init 생성자와 데이터 출력 메서드(print_info) 필요
init 생성자 :
- 매개변수로 노드에 담을 데이터를 받아옴
- 왼쪽, 오른쪽 자식 노드를 가리키는 참조와 데이터를 담을 데이터 변수
데이터 출력 메서드(print_info) :
- 우선 해당 노드의 데이터 출력
- 왼쪽(오른쪽) 자식이 비어있지 않은지 확인 후, 비어있지 않으면 왼쪽(오른쪽) 자식 데이터 출력
  (self.left하면 해당 노드의 주소가 찍히기 때문에 .data로 데이터를 출력)
- 왼쪽(오른쪽) 자식이 비어있는 경우 비었다는 문구 출력
- 양쪽 자식이 모두 비었는 경우, 리프노드라는 문구 출력

2. 루트 노드 생성 : BinarytreeNode 클래스를 사용해 루트 노드 인스턴스 생성

3. 서브 노드 생성 : BinarytreeNode 클래스를 사용해 서브 노드 인스턴스들 생성
(아직 노드들이 연결되지 않은 상태 = 메모리에 노드들이 흩어진 상태)

4. 생성한 루트 노드와 서브 노드들 연결 : root.left = node2 처럼 "객체 자체"를 연결해야 함

5. 클래스 메서드를 사용하여 데이터 출력

# 이진 트리 구현
# 1. Node 클래스
class BinarytreeNode:
    def __init__(self, data):    
        self.left = None        # 왼쪽 자식 노드를 가리킴
        self.data = data        # 노드에 저장할 데이터
        self.right = None       # 오른쪽 자식 노드를 가리킴

    # 데이터 출력할 메서드
    def print_info(self):
        print("노드의 데이터 : ", self.data)              # 해당 노드의 데이터 출력

        if self.left is not None:                       # 해당 노드의 왼쪽 자식이 비어있지 않은지 확인
            print("노드의 왼쪽 : ", self.left.data)       # 비어있지 않으면 왼쪽 자식의 데이터 출력
                                                        # self.left를 하면 주소값이 찍히기 때문에 .data로 데이터를 출력
        else:
            print("노드의 왼쪽이 비었습니다")               # 해당 노드의 왼쪽 자식이 비어있는 경우

        if self.right is not None:                      # 해당 노드의 오른쪽 자식이 비어있지 않은지 확인
            print("노드의 오른쪽 : ", self.right.data)    # 비어있지 않으면 오른쪽 자식의 데이터 출력
        else:
            print("노드의 오른쪽이 비었습니다")             # 해당 노드의 오른쪽 자식이 비어있는 경우

        if self.left is None and self.right is None:    # 양쪽 자식이 모두 비어있는 경우
            print(f"{self.data}는 leaf 노드입니다.")      # 리프노드라고 출력

        print("=" * 25)

# 2. 루트 노드 생성
root = BinarytreeNode("A")

# 3. 서브 노드 생성
node2 = BinarytreeNode("B")
node3 = BinarytreeNode("C")
node4 = BinarytreeNode("D")
node5 = BinarytreeNode("E")
node6 = BinarytreeNode("F")
node7 = BinarytreeNode("G")
node8 = BinarytreeNode("H")

# 4. 트리 연결
root.left = node2     # A의 왼쪽에 B
root.right = node3    # A의 오른쪽에 C

node2.left = node4    # B의 오른쪽에 D

node3.left = node5    # C의 왼쪽에 E
node3.right = node6   # C의 오른쪽에 F

node5.left = node7    # E의 왼쪽에 G

node6.right = node8   # F의 오른쪽에 H

# 5. 데이터 출력
root.print_info()
node2.print_info()
node3.print_info()
node4.print_info()
node5.print_info()
node6.print_info()
node7.print_info()
node8.print_info()

이진 트리를 구현해보았으니 일반 트리도 구현해보자

1. class TreeNode 구현

init 생성자와 자식 노드 추가 메서드(add_child), 데이터 출력 메서드(print_info) 3가지가 필요
init 생성자 :
- 매개변수로 노드에 담을 데이터를 받아옴
- 자식 노드가 이진 트리처럼 개수가 정해져 있지 않기 때문에 자식 노드 객체를 담기 위한 리스트를 준비
자식 노드 추가 메서드(add_child) :
- 클래스 밖에서 노드를 생성 후, 각 자식 노드 객체들을 부모 노드의 children 리스트에 삽입
- children 리스트니까 append 메서드 사용
- 이진 트리와 마찬가지로 노드의 데이터를 담는 것이 아닌 "TreeNode 객체 자체"를 삽입
데이터 출력 메서드(print_info) :
- 우선 해당 노드의 데이터 출력
- 자식 노드들은 children 리스트 안에 담겨 있으므로 반복문을 사용하여 리스트 요소들을 출력
- children 리스트의 길이가 0이면 leaf 노드라는 문구 출력

2. 루트 노드 생성 : TreeNode 클래스를 사용해 루트 노드 인스턴스 생성

3. 서브 노드 생성 : TreeNode 클래스를 사용해 서브 노드 인스턴스들 생성

4. 클래스 메서드를 사용하여 생성한 루트 노드와 서브 노드들 연결 :

자식 노드들을 담는 children 리스트에 문자열이나 데이터가 아닌 TreeNode로 생성한 객체들을 넣어준다.

5. 클래스 메서드를 사용하여 데이터 출력

# 일반 트리 구현
# 1. Node 클래스
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []          # 해당 노드의 자식 노드들을 담을 빈 리스트
                                    # (이진 트리처럼 2개가 아닌 3개 이상의 객체를 담기 위해 리스트로 생성)

    # 자식 노드 추가 메서드
    def add_child(self, child_node):        # 자식 노드를 생성 후, 메서드를 사용하여 각 객체를 children에 담아줌
        self.children.append(child_node)    # 리스트이므로 append 메서드 사용하여 리스트 맨 끝에 각 요소 삽입

    # 데이터 출력 메서드
    def print_info(self):
        print(f"노드의 데이터 : {self.data}")               # 해당 노드의 데이터 출력
        print("자식 노드 : ", end = "")                    # 자식 노드들을 출력하자 (엔터 삭제)

        for i in range(len(self.children)):             # 자식 노드가 들어있는 리스트(children)의 길이만큼 반복
            print(self.children[i].data, end = ", ")    # children 안의 객체들의 데이터를 출력

        if len(self.children) == 0:
            print()
            print(f"{self.data}는 leaf 노드입니다.")

        print("\n"+"=" *  30)

# 2. 루트 노드 생성
root = TreeNode("A")

# 3. 서브 노드 생성
node2 = TreeNode("B")
node3 = TreeNode("C")
node4 = TreeNode("D")
node5 = TreeNode("E")
node6 = TreeNode("F")
node7 = TreeNode("G")
node8 = TreeNode("H")
node9 = TreeNode("I")
node10 = TreeNode("J")

# 4. 트리 연결
root.add_child(node2)
root.add_child(node3)
root.add_child(node4)

node2.add_child(node5)
node2.add_child(node6)
node2.add_child(node7)

node3.add_child(node8)

node4.add_child(node9)
node4.add_child(node10)

# 5. 데이터 출력
root.print_info()
node2.print_info()
node3.print_info()
node4.print_info()
node5.print_info()
node6.print_info()
node7.print_info()
node8.print_info()
node9.print_info()
node10.print_info()

초기 일반 트리 구현 코드의 수정 사항
1. "자식노드 : B, C, D," 처럼 마지막 요소 뒤에도 콤마가 찍힘
2. "_는 leaf 노드입니다." 출력 후, 문구와 구분선 사이의 공백
3. leaf 노드 판별하는 if문을 조금 더 간단하게
문제점 수정 후 코드

# 문제점 수정 후 TreeNode 클래스 코드
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []          

    # 자식 노드 추가 메서드
    def add_child(self, child_node):
        self.children.append(child_node)

    # 데이터 출력 메서드
    def print_info(self):
        print(f"노드의 데이터 : {self.data}")
        print("자식 노드 : " + ",".join(i.data for i in self.children)) # 1 .join 사용

        if not self.children:       # 3. not으로 단순화
            print(f"{self.data}는 leaf 노드입니다.")

        print("=" * 30)             # 2. 불필요한 공백 삭제

* 선형 구조 : 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고
* 비선형 구조 : 표현에 초점이 맞춰져 있음 (ex. 폴더 구조)

[과제 후기]

* 이진 트리 초기 구현 시 print_info()의 if문을 self.left.data로 하여 에러가 발생하였다. self.left 노드가 없는데 빈 노드의 데이터를 검사하게 되어 에러가 발생했다는 것이었다. data가 비었는지를 확인하는 것이 아닌

1. 왼쪽 자식이 존재하는지를 먼저 검사한 후

2. 존재하면 왼쪽 자식의 데이터를 출력

하는 방식으로 구현해야 에러가 발생하지 않음 (오른쪽도 마찬가지)

* 이진 트리 초기 구현 시 트리 연결하는 부분에서 root.left = node2.data 이렇게 노드 객체를 직접 연결하는 것이 아닌 각 데이터를 연결하여 제대로 된 연결을 하지 못했다. 저렇게 연결하게되면 root.left = "B" 처럼 문자열만 저장하게 되어 트리를 연결하는 것이 아니게 된다. 그러므로 left와 right는 항상 BinarytreeNode 객체를 가리키도록 해야 한다.

* 트리 구현은 과거에도 직접 해본적이 없었지만 이번 훈련 과정에서 해볼 수 있게 되었다. 이진 트리 초기 구현 시 C언어로 구현된 코드를 보고 파이썬으로 고쳐보면서 1차 작성해본 후 클로드를 이용해 정답 코드말고 힌트만 받아서 해보니 시간은 정말 오래 걸렸지만 그만큼 뿌듯했다.

'KDT > 과제' 카테고리의 다른 글

[12일차 과제] 시간복잡도, 공간복잡도 (0)	2026.06.07
[11일차 과제] 자료구조(해시 테이블) (0)	2026.06.04
[9일차 과제] 자료구조(연결 리스트, 이중 연결 리스트) (0)	2026.06.01
[8일차 과제] 자료구조(배열, 스택, 큐) (0)	2026.05.31
[4일차 과제] (0)	2026.05.22

프로그래머가 되고 싶은 감자

프로그래머가 되고 싶은 감자

태그

최근글

댓글

공지사항

아카이브

1. 트리(Tree)란?

2. 트리의 주요 용어 정리 (with 그림)

3. 트리 순회 방식

4. 파이썬으로 간단한 트리 구현

'KDT > 과제' 카테고리의 다른 글

관련글

티스토리툴바