Tree 트리

Tree

트리는 계층 구조를 표현하는 비선형 자료구조이다. 트리는 루트 노드에서 시작해 여러 개의 자식 노드를 가질 수 있으며, 트리의 각 노드는 자식 노드와 연결될 수 있다. 부모-자식 관계로 구성되어 계층적인 데이터를 표현할 때 유용하며, 특히 이진 트리(Binary Tree) 형태가 많이 사용된다.

트리의 주요 개념

1. 루트 노드(Root Node): 트리의 최상단 노드.
2. 자식 노드(Child Node): 다른 노드로부터 연결된 하위 노드.
3. 부모 노드(Parent Node): 자식 노드를 가진 노드.
4. 잎(Leaf): 자식 노드가 없는 노드.

트리의 가장 일반적인 형태인 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 구조

트리 구현 예시

# 노드를 나타내는 클래스
class Node:
    def __init__(self, value):
        self.value = value  # 노드의 값
        self.left = None    # 왼쪽 자식 노드
        self.right = None   # 오른쪽 자식 노드

# 이진 트리를 생성하는 함수
def create_binary_tree():
    # 루트 노드 생성
    root = Node(1)
    
    # 레벨 1의 자식 노드 추가
    root.left = Node(2)
    root.right = Node(3)
    
    # 레벨 2의 자식 노드 추가
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    
    return root

위의 코드는 다음과 같은 형태의 트리를 만든다.

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

• 노드 1은 루트 노드
• 노드 2와 3은 1의 자식 노드
• 노드 4, 5, 6, 7은 잎 노드로, 자식이 없다.

트리 순회(Tree Traversal)

트리 순회는 트리 구조의 모든 노드를 방문하는 방법이다. 순회 방식에는 주로 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)가 있다.

1. 전위 순회 (Pre-order)

전위 순회는 루트 -> 왼쪽 -> 오른쪽 순으로 방문한다.

def pre_order(node):
    if node:
        print(node.value, end=" ")  # 현재 노드 방문
        pre_order(node.left)       # 왼쪽 서브트리 순회
        pre_order(node.right)      # 오른쪽 서브트리 순회

# 사용 예시
root = create_binary_tree()
print("전위 순회 결과:")
pre_order(root)  # 결과: 1 2 4 5 3 6 7

2. 중위 순회 (In-order)

중위 순회는 왼쪽 -> 루트 -> 오른쪽 순으로 방문한다.

def in_order(node):
    if node:
        in_order(node.left)        # 왼쪽 서브트리 순회
        print(node.value, end=" ")  # 현재 노드 방문
        in_order(node.right)       # 오른쪽 서브트리 순회

print("\n중위 순회 결과:")
in_order(root)  # 결과: 4 2 5 1 6 3 7

3. 후위 순회 (Post-order)

후위 순회는 왼쪽 -> 오른쪽 -> 루트 순으로 방문한다.

def post_order(node):
    if node:
        post_order(node.left)      # 왼쪽 서브트리 순회
        post_order(node.right)     # 오른쪽 서브트리 순회
        print(node.value, end=" ")  # 현재 노드 방문

print("\n후위 순회 결과:")
post_order(root)  # 결과: 4 5 2 6 7 3 1

설명

• 전위 순회: 노드의 방문 순서가 루트에서 시작하므로, 트리의 구조를 출력하거나 저장할 때 유용하다.
• 중위 순회: 이진 탐색 트리(BST)에서 중위 순회를 사용하면 모든 노드를 오름차순으로 정렬된 순서로 방문할 수 있다.
• 후위 순회: 서브트리의 모든 노드를 방문한 후 부모 노드를 방문하므로, 하위 노드를 먼저 처리해야 하는 경우 유용하다.

게임 스킬 트리 코드 구현

RPG 게임의 스킬 트리

RPG 게임에서는 캐릭터가 특정 스킬을 배우거나 업그레이드할 때, 특정 조건이 충족되어야 하는 경우가 많이 있다. 예를 들어, 기본 스킬을 먼저 습득해야 고급 스킬을 배울 수 있는 구조이다. 이를 트리 구조로 표현하면 각 스킬은 노드가 되고, 부모-자식 관계로 스킬들이 계층적으로 연결된다.

스킬 트리 구조와 코드 예시

class SkillNode:
    def __init__(self, name, level_required, description):
        self.name = name                   # 스킬 이름
        self.level_required = level_required  # 스킬 습득에 필요한 레벨
        self.description = description     # 스킬 설명
        self.children = []                 # 하위 스킬 목록

    # 자식 노드(하위 스킬) 추가
    def add_child(self, child):
        self.children.append(child)

    # 스킬 정보를 출력하는 메소드
    def display(self, level=0):
        indent = " " * (level * 4)
        print(f"{indent}- {self.name} (레벨 {self.level_required} 이상 필요): {self.description}")
        for child in self.children:
            child.display(level + 1)

# 스킬 트리 생성 함수
def create_skill_tree():
    # 기본 스킬
    root = SkillNode("기본 공격", 1, "일반 공격으로 적에게 피해를 줍니다.")
    
    # 1레벨 스킬
    skill1 = SkillNode("파워 스트라이크", 2, "강력한 공격으로 추가 피해를 줍니다.")
    skill2 = SkillNode("방어 자세", 2, "방어력을 일시적으로 증가시킵니다.")
    
    # 2레벨 스킬
    skill1_1 = SkillNode("폭발 스트라이크", 4, "더 큰 피해를 주는 강력한 공격.")
    skill2_1 = SkillNode("철벽 방어", 4, "방어력을 크게 증가시킵니다.")

    # 스킬 트리 구축
    root.add_child(skill1)
    root.add_child(skill2)
    skill1.add_child(skill1_1)
    skill2.add_child(skill2_1)
    
    return root

위의 코드에서 SkillNode 클래스는 각 스킬을 표현한다. 각 스킬은 이름, 요구 레벨, 설명, 그리고 하위 스킬들을 가질 수 있다. create_skill_tree() 함수는 간단한 스킬 트리를 생성하고 트리 구조를 반환한다.

스킬 트리 출력

이제 만들어진 스킬 트리를 출력해 보겠다. display() 메소드를 호출하여 트리 구조를 계층적으로 표현할 수 있다.

# 스킬 트리 생성 및 출력
skill_tree = create_skill_tree()
print("스킬 트리:")
skill_tree.display()

출력 결과는 다음과 같은 계층 구조를 가진다.

스킬 트리:
- 기본 공격 (레벨 1 이상 필요): 일반 공격으로 적에게 피해를 줍니다.
    - 파워 스트라이크 (레벨 2 이상 필요): 강력한 공격으로 추가 피해를 줍니다.
        - 폭발 스트라이크 (레벨 4 이상 필요): 더 큰 피해를 주는 강력한 공격.
    - 방어 자세 (레벨 2 이상 필요): 방어력을 일시적으로 증가시킵니다.
        - 철벽 방어 (레벨 4 이상 필요): 방어력을 크게 증가시킵니다.

설명

• 기본 공격을 배우면 파워 스트라이크와 방어 자세라는 새로운 스킬을 배울 수 있다.
• 파워 스트라이크를 배운 후에는 더 강력한 폭발 스트라이크를 배울 수 있고, 방어 자세를 배우면 철벽 방어 스킬을 사용할 수 있다.
• 각 스킬은 특정 레벨 이상일 때 배울 수 있도록 설정되어 있으며, 이처럼 특정 조건을 가지는 트리 구조를 통해 계층적인 스킬 습득 과정을 쉽게 관리할 수 있다.