연결리스트, 트리, 이진트리 순회

배열 → 스택
배열 → 큐
배열 → 원형 큐

연결리스트 = 노드들을 포인터로 연결한 구조
트리 = 부모-자식 관계를 가진 계층 구조
이진트리 = 자식이 최대 2개인 트리
순회 = 트리의 모든 노드를 정해진 순서로 방문하는 것

배열의 한계
→ 연결리스트의 필요성
→ 노드와 포인터
→ 단순 연결리스트
→ 삽입과 삭제
→ 원형 연결리스트
→ 이중 연결리스트
→ 트리의 기본 개념
→ 이진트리
→ 전위순회, 중위순회, 후위순회

int arr[5] = {10, 20, 30, 40, 50};

arr[0] arr[1] arr[2] arr[3] arr[4]
 10     20     30     40     50

인덱스로 바로 접근 가능

arr[3]

O(1)

[10, 20, 30, 40, 50]

[10, 20, 25, 30, 40, 50]

O(n)

10 20 30 40

[10 | 다음주소] → [20 | 다음주소] → [30 | 다음주소] → NULL

데이터 + 링크

[ data | link ]

[ 10 | 다음 노드 주소 ]

struct Node {
    int data;
    struct Node *next;
};

구조체 = data와 next를 하나로 묶음
포인터 = 다음 노드의 주소 저장

head → [10 | next] → [20 | next] → [30 | NULL]

head = 리스트의 입구

NULL = 다음 노드가 없음

마지막 노드의 next = NULL

배열 = 찾기는 빠르지만 중간 삽입·삭제가 불편
연결리스트 = 찾기는 느리지만 삽입·삭제가 유리

head → [10 | next] → [20 | next] → [30 | NULL]

한 방향으로만 이동 가능

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *head = NULL;

head = NULL

Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = 10;
newNode->next = NULL;

newNode->data = (*newNode).data

malloc
free

Node *p = (Node *)malloc(sizeof(Node));

Node 하나를 저장할 공간을 메모리에 만들고,
그 주소를 p에 저장합니다.

free(p);

p가 가리키던 메모리를 다시 사용 가능하게 돌려줍니다.

head → 첫 번째 노드 → 두 번째 노드 → 세 번째 노드 → NULL

Node *p = head;

while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
}

p가 현재 노드를 가리킵니다.
p->data를 출력합니다.
p = p->next로 다음 노드로 이동합니다.
NULL을 만나면 끝납니다.

O(n)

head → [20] → [30] → NULL

[10]

[10] → [20] → [30] → NULL

head → [10] → [20] → [30] → NULL

newNode->next = head;
head = newNode;

새 노드를 기존 첫 노드 앞에 연결
head를 새 노드로 변경

O(1)

head → [10] → [20] → [30] → NULL

[40 | NULL]

[30 | NULL]

head → [10] → [20] → [30] → [40] → NULL

Node *p = head;

while (p->next != NULL) {
    p = p->next;
}

p->next = newNode;

O(n)

head → [10] → [20] → [30] → NULL

[25]

prev → [20]

newNode->next = prev->next;
prev->next = newNode;

newNode->next = 30
20->next = newNode

head → [10] → [20] → [25] → [30] → NULL

prev->next = newNode;
newNode->next = prev->next;

head → [10] → [20] → [30] → NULL

head → [10] → [30] → NULL

prev->next = target->next;
free(target);

이전 노드가 삭제할 노드의 다음 노드를 가리키게 합니다.
삭제할 노드는 free로 반환합니다.

head → [10] → [20] → [30] → NULL

Node *target = head;
head = head->next;
free(target);

head → [20] → [30] → NULL

새 노드를 기존 노드 사이에 끼워 넣습니다.

newNode->next = prev->next;
prev->next = newNode;

삭제할 노드를 건너뛰도록 연결합니다.

prev->next = target->next;
free(target);

연결리스트는 데이터를 밀지 않습니다.
포인터를 바꿉니다.

배열: 접근 O(1), 중간 삽입·삭제 O(n)
연결리스트: 접근 O(n), 연결 위치를 알면 삽입·삭제 O(1)

head → [10] → [20] → [30] → NULL

마지막 노드의 next = head

while (p != NULL)

[prev 없음 | data | next]

[prev | data | next]

NULL ← [10] ⇄ [20] ⇄ [30] → NULL

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

앞으로도 이동 가능
뒤로도 이동 가능

포인터가 하나 더 필요하므로 메모리를 더 씁니다.
삽입·삭제 시 prev와 next를 모두 조정해야 합니다.

연결리스트 = 포인터로 노드를 연결하는 기본 구조

        A
      /   \
     B     C
    / \     \
   D   E     F

A = 루트

B의 부모 = A
D의 부모 = B

A의 자식 = B, C
B의 자식 = D, E

B와 C는 형제
D와 E는 형제

D, E, F = 단말노드

A, B, C = 내부노드

A의 차수 = 2
B의 차수 = 2
C의 차수 = 1
D의 차수 = 0

트리의 차수 = 2

A = 레벨 0
B, C = 레벨 1
D, E, F = 레벨 2

A = 레벨 1
B, C = 레벨 2
D, E, F = 레벨 3

높이 = 트리가 몇 층까지 내려가는가

1. 사이클이 없습니다.
2. 하나의 루트가 있습니다.
3. 부모-자식 계층 구조입니다.
4. 노드가 n개이면 간선은 n-1개입니다.

트리의 노드 수가 n개이면 간선 수는 n - 1개

A, B, C, D, E, F = 6개
간선 = 5개

자식 수가 0개, 1개, 2개까지 가능
3개는 불가능

        A
      /   \
     B     C
    / \     \
   D   E     F

왼쪽 자식
오른쪽 자식

노드가 자식을 여러 개 가질 수 있습니다.

        A
   /    |    \
  B     C     D

자식이 최대 2개

        A
      /   \
     B     C

        A
      /   \
     B     C
    / \   / \
   D   E F   G

모든 내부 노드가 자식 2개를 가집니다.
모든 단말 노드가 같은 레벨에 있습니다.

노드 수 = 2^(h+1) - 1

레벨 0: 1개
레벨 1: 2개
레벨 2: 4개
총 1 + 2 + 4 = 7개

        A
      /   \
     B     C
    / \   /
   D   E F

        A
      /   \
     B     C
      \     \
       E     F

포화 = 전부 꽉 참
완전 = 마지막만 왼쪽부터 채워짐

부모 i
왼쪽 자식 = 2i
오른쪽 자식 = 2i + 1
부모 = i / 2

        A(1)
      /      \
   B(2)      C(3)
   / \       /
D(4) E(5)  F(6)

B의 인덱스 = 2
B의 왼쪽 자식 = 4 → D
B의 오른쪽 자식 = 5 → E
C의 왼쪽 자식 = 6 → F

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

왼쪽 자식 주소 + 데이터 + 오른쪽 자식 주소

[ left | data | right ]

        A
      /   \
     B     C

A.left = B
A.right = C

B.left = NULL
B.right = NULL
C.left = NULL
C.right = NULL

arr[0], arr[1], arr[2], ...

        A
      /   \
     B     C
    / \   / \
   D   E F   G

전위순회
중위순회
후위순회

전위 = 루트 먼저
중위 = 루트 가운데
후위 = 루트 나중

        A
      /   \
     B     C
    / \   / \
   D   E F   G

A의 왼쪽 = B
A의 오른쪽 = C
B의 왼쪽 = D
B의 오른쪽 = E
C의 왼쪽 = F
C의 오른쪽 = G

루트 → 왼쪽 → 오른쪽

현재 노드를 먼저 방문합니다.
그다음 왼쪽 서브트리.
그다음 오른쪽 서브트리.

        A
      /   \
     B     C
    / \   / \
   D   E F   G

A

A B

A B D

A B D E

A B D E C

A B D E C F

A B D E C F G

A B D E C F G

ABDECFG

왼쪽 → 루트 → 오른쪽

왼쪽 서브트리를 먼저 방문합니다.
그다음 현재 노드.
그다음 오른쪽 서브트리.

        A
      /   \
     B     C
    / \   / \
   D   E F   G

왼쪽 B 서브트리 → A → 오른쪽 C 서브트리

D → B → E

F → C → G

D B E A F C G

DBEAFCG

왼쪽 → 오른쪽 → 루트

왼쪽 서브트리를 먼저 방문합니다.
오른쪽 서브트리를 방문합니다.
마지막에 현재 노드를 방문합니다.

        A
      /   \
     B     C
    / \   / \
   D   E F   G

왼쪽 B 서브트리 → 오른쪽 C 서브트리 → A

D → E → B

F → G → C

D E B F G C A

DEBFGCA

        A
      /   \
     B     C
    / \   / \
   D   E F   G

전위: ABDECFG
중위: DBEAFCG
후위: DEBFGCA

        A
      /   \
     B     C

A B C

B A C

B C A

전위(node):
    node 방문
    왼쪽 전위
    오른쪽 전위

중위(node):
    왼쪽 중위
    node 방문
    오른쪽 중위

후위(node):
    왼쪽 후위
    오른쪽 후위
    node 방문

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void preorder(TreeNode *root) {
    if (root != NULL) {
        printf("%c ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

루트 출력
왼쪽
오른쪽

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

왼쪽
루트 출력
오른쪽

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

왼쪽
오른쪽
루트 출력

1. 루트를 찾습니다.
2. 왼쪽 서브트리를 먼저 봅니다.
3. 오른쪽 서브트리를 봅니다.
4. 후위순회라면 루트는 마지막에 씁니다.

왼쪽 → 오른쪽 → 루트

        A
      /   \
     B     C
    /     /
   D     E

D B

E C

A

D B E C A

DBECA

전위: A B D E C

루트 = A

D E B C A

루트 = A

왼쪽 서브트리의 값 < 루트 값 < 오른쪽 서브트리의 값

        50
      /    \
    30      70
   /  \    /  \
 20   40  60   80

30, 20, 40

70, 60, 80

        50
      /    \
    30      70
   /  \    /  \
 20   40  60   80

왼쪽 → 루트 → 오른쪽

20 30 40 50 60 70 80

이진 탐색 트리 + 중위순회 = 오름차순 출력

A + B * C

      +
     / \
    A   *
       / \
      B   C

+ A * B C

A + B * C

A B C * +

전위순회 = 전위표기식
중위순회 = 중위표기식
후위순회 = 후위표기식

struct Node {
    int data;
    struct Node *next;
};

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

연결리스트 = 한 줄로 연결
트리 = 가지처럼 연결

배열 = 연속 저장, 인덱스 접근 빠름
연결리스트 = 포인터 연결, 삽입·삭제 유리

세 번째 노드를 보려면 head부터 따라가야 합니다.

next = NULL

마지막 노드의 next = head

newNode->next = prev->next;
prev->next = newNode;

p->data

(*p).data

루트 = 부모가 없는 노드

leaf node = 자식 0개

포화 = 전부 꽉 참
완전 = 마지막 레벨만 덜 찰 수 있고 왼쪽부터 채움

전위 = 루트 먼저
중위 = 루트 가운데
후위 = 루트 마지막

후위 = 왼쪽 → 오른쪽 → 루트

노드들을 포인터로 연결한 선형 자료구조

데이터 + 링크

struct Node {
    int data;
    struct Node *next;
};

리스트의 첫 번째 노드를 가리키는 포인터

각 노드가 다음 노드만 가리킴

마지막 노드가 첫 번째 노드를 가리킴

이전 노드와 다음 노드를 모두 가리킴

부모-자식 관계를 가진 계층적 자료구조

각 노드의 자식이 최대 2개인 트리

마지막 레벨을 제외하고 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워진 트리

루트 → 왼쪽 → 오른쪽

왼쪽 → 루트 → 오른쪽

왼쪽 → 오른쪽 → 루트

연결리스트 = 포인터로 연결
트리 = 계층 구조
전위 = 루트 먼저
중위 = 루트 가운데
후위 = 루트 마지막

마지막 레벨을 제외한 모든 레벨이 채워져 있고,
마지막 레벨은 왼쪽부터 채워진 이진트리

        A
      /   \
     B     C
    / \   / \
   D   E F   G