[1주차 TIL] KnockOn Bootcamp - 트리

🔍트리(Tree) : 구조체 기반 메모리 구조 분석의 시작

📖 개요

트리(Tree)는 소프트웨어 내부 데이터 구조 중 가장 중요한 계층적 구조의 핵심이다. 트리는 프로그램의 다양한 데이터 흐름, 상태 변화, 구조 관계를 표현할 수 있으며, 리버싱 관점에서 이를 이해하고 분석하는 것은 실질적인 코드 흐름 해석, 오브젝트 파악, 루트 노드 기반 추적의 필수 능력이다.

 

본 장에서는 트리의 기초부터 순회, 구조체 구현, 그리고 리버싱 실전에서 트리 구조가 어떻게 분석되는지를 학습한다.

---

📌 1. 트리란?

트리는 노드(Node) 들이 연결되어 구성되는 비선형적이며 계층적인 자료구조이다. 각 노드는 다른 노드와 연결되어 있으며, 일반적으로 하나의 부모 노드와 0개 이상의 자식 노드를 가진다.

 

트리의 주요 특징:

• 루트 노드(Root): 트리의 시작점이 되는 노드
• 부모 노드(parent): 하위 노드를 가진 노드
• 자식 노드(child): 특정 노드에 의해 연결된 하위 노드
• 리프 노드(Leaf): 자식이 없는 노드
• 서브 트리(Subtree): 하나의 노드를 루트로 하는 부분 트리
• 비순환성(Acyclic): 트리는 사이클을 가지지 않는다

---

📖 2. 리버싱 관점에서 트리 구조의 중요성

리버싱 과정에서 트리는 다음과 같은 영역에서 자주 등장한다:

영역	사용 예
게임 해킹	오브젝트 관리 트리, 장비 계층 구조
악성코드 분석	명령 체계 및 조건 분기 표현
운영체제	윈도우 핸들 트리, 윈도우 메시지 큐
시스템 구조 분석	레지스트리 트리, 디바이스 노드 트리
UI 구성	윈도우 클래스 계층, HWND 트리 구조

리버서가 실행 파일을 분석할 때 특정 구조가 트리 기반인지 파악하면, 루트 노드 주소 → 재귀적 트리 순회를 통해 전체 흐름을 단시간에 파악할 수 있다.

---

🧠 3. 트리에서 사용하는 용어 정리

용어	설명
Root	트리의 최상단 노드
Parent	자식 노드를 가지는 노드
Child	부모로부터 연결된 노드
Sibling	동일 부모를 가지는 노드
Leaf	자식이 없는 노드
Depth	루트부터 특정 노드까지의 거리
Height	특정 노드로부터 가장 깊은 노드까지 거리
Degree	특정 노드가 가지는 자식 수
Subtree	특정 노드를 루트로 하는 트리

💡 리버싱 실전 팁:
구조체 분석 시 구조체 안에 left, right 또는 next, prev, parent 같은 필드가 있다면 트리나 리스트 기반 자료구조를 의심해야 한다.

---

🧱 4. 이진 트리와 이진 탐색 트리

✔ 이진 트리 (Binary Tree)

• 각 노드가 최대 두 개의 자식을 가지는 트리 구조
• 일반적으로 left, right 포인터로 구현됨

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

• 모든 레벨이 채워지고, 마지막 레벨은 왼쪽부터 차례로 채워짐
• 배열 기반 힙 구조에서 자주 사용됨 (Heap Sort, Priority Queue 등)

✔ 이진 탐색 트리 (Binary Search Tree, BST)

• 왼쪽 자식 < 부모 < 오른쪽 자식
• 데이터 탐색, 삽입, 삭제에 O(log n) 성능 제공
• 악성코드 내부 주소 테이블, 게임 내 NPC 탐색 트리 등에 응용

---

🔍 5. 트리 순회(Tree Traversal) 알고리즘

트리 구조를 해석하거나 데이터 분석을 할 때 트리 순회 알고리즘이 필수다. 리버서 입장에서 중요한 것은, 재귀 호출, 스택 사용 여부, 노드 순서 흐름이다.

순회 방식	순서	사용 예
전위 순회	Root → Left → Right	디버깅 시 루트부터 메모리 구조 재구성
중위 순회	Left → Root → Right	정렬된 탐색 트리 재구성
후위 순회	Left → Right → Root	구조체 해제 시, 자식부터 해제

🧪 전위 순회 예시

void preorder(Node* node) {
    if (!node) return;
    printf("%d ", node->data);
    preorder(node->left);
    preorder(node->right);
}

🧪 중위 순회 예시

void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

🧪 후위 순회 예시

void postorder(TreeNode* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

🔧 6. 트리 구조체 구현 및 실습

📁 구조체 정의

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

📁 노드 생성

Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

📁 트리 구성 & 순회

int main() {
    Node* root = createNode(10);
    root->left = createNode(6);
    root->right = createNode(15);
    root->left->left = createNode(3);
    root->left->right = createNode(8);

    printf("Preorder: ");
    preorder(root);         // 출력: 10 6 3 8 15
}

---

🔬 7. 실전 리버싱 시 트리 분석 예시

예: 게임 구조체 분석

typedef struct Object {
    int objectId;
    struct Object* left;
    struct Object* right;
} Object;

• Cheat Engine이나 x64dbg에서 메모리 덤프 시,
  특정 오브젝트 주소에서 +0x4, +0x8이 포인터라면 이진 트리 구조임을 확인 가능
• 루트 주소부터 재귀적으로 순회하면 전체 오브젝트 체계를 추출 가능

---

🧩 도전 과제

1. 사용자 입력으로 이진 탐색 트리를 구성하고, 중위 순회 결과를 출력하라.
2. 구조체 기반으로 트리를 구성한 후 높이와 노드 수를 재귀적으로 구하는 함수를 작성하라.
3. 포인터를 이용해 메모리 주소 기반으로 트리를 추적하는 실습을 설계하라.

---

🧠 정리

• 트리는 비선형 구조지만 메모리 상에서는 구조체로 직렬화되어 저장된다.
• 리버서 관점에서 트리는 메모리 해킹, 구조 해석, 객체 분석에 있어 매우 중요한 분석 단서이다.
• 트리 순회, 구성 원리를 알면 어셈블리 추적, Cheat Engine 분석, 구조체 재구성이 가능해진다.