[자료구조] 7강 - 트리

✅ 1. 트리의 개념

(1) 트리의 정의

• 트리는 계급적인 특성을 가지는 계층화를 통해 검색을 편리하게 하기 위한 자료구조로 볼 수 있음.

---

✅ 2. 트리의 표현 방법

(1) 트리의 구성

• 노드: 트리의 항목/트리에 저장되는 데이터의 묶음이다. 쉽게말해, 위 이미지에서 A, B, C... 각각을 의미 할 수 있음.
• 부모노드: 상하 계층구조 및 직접연결 된 노드 구조에서 해당 노드의 상위계층을 부모 노드라고 함.
• 자식노드: 부모노드와 반대로 특정 노드의 하위계층을 자식노드라고 함.
• ( 특징은 부모노드와 자식노드는 직접 연결된 구조에서만 가능하므로 부모는 반드시 노드 1개가 될 수 있음. )
• 루트노드: 트리의 최상휘 노드로 부모가 없는 노드로 볼 수 있다.
• 서브트리: 부모 노드를 삭제하면 생기는 트리들을 의미한다. 쉽게말해, B의 서브트리는 D, H, I or E 가 될 수 있음.
• ( 또한, B의 서브트리라고 하면 B가 루트가 되면서 B를 포함한 B or D, H, I or E 가 서브트리에 포함된 노드로 봄 )
• 잎 노드: 트리의 맨 끝에 있으면서, 자신의 서브트리나 자식 노드를 갖지 않는 노드를 의미함.

(2) 진입 및 진출 차수

• 차수: 하나의 노드에서 연결 되어 있는 선의 개수로 볼 수 있음. ( 즉, A 의 차수는 2개로 볼 수 있음. )
• 진입차수: 특정 노드에 접근하는 차수를 진입차수라고함.
• 진출차수: 특정 노드에서 다른 노드에 접근하는 차수를 진출차수라고함.
• 즉, 루트 노드는 항상 진입 차수가 0 일 수 있음.
• 또한, 루트를 제외한 모든 노드의 진입 차수는 1, 입 노드의 진출 차수는 항상 0 이 될 수 있음.

(3) 내부 노드 및 형제 노드

• 내부 노드: 루트 노드, 잎 노드가 아닌 노드를 모두 내부 노드로 볼 수 있음.
• 형제 노드: 같은 부모를 갖는 노드들을 의미함. 즉, 같은 부모를 가지기에 같은 레벨의 노드로도 볼 수 있음.

(4) 트리의 레벨

• 노드의 레벨: 루트로부터 그 노드까지 이어진 선(경로)의 길이를 의미함.
• ( 루트 노드의 레벨은 1 또는 0 으로 정의하는 경우가 많음 여기서는 0레벨로 봄 )
• 트리의 깊이: 트리의 최대 레벨에 1을 더하면 트리의 깊이를 알 수 있음. ( 즉, 3 level + 1 = 4 -> 깊이: 4 )
• ( 루트로부터 특정 노드까지의 거리(간선 수)를 의미한다. )
• ( 루트의 깊이는 0으로 두는 게 일반적이며, 루트의 자식은 1, 루트의 손자는 2로 볼 수 있음. )
• 트리의 높이: 루트 노드의 높이, 즉 전체 트리의 가장 긴 경로의 간선 수를 의미함.
• 노드의 높이: 해당 노드에서 가자아 먼 리프 노드까지의 간선 수

---

✅ 3. 추상 자료형

• 트리 객체의 정의: 루트 노드를 갖는 유한 리스트를 트리 객체로 정의함.

• 이러한 추상자료형을 가지고 트리의 자료구조를 구현하게 됨.

---

✅ 4. 이진 트리

(1) 이진 트리의 정의

• 모든 노드의 차수가 2 이하인 트리를 의미한다. 즉, 노드의 차수가 2개를 넘어가면 이진 트리로 안봄.
• - 이진 트리는 수학적으로 이진 트리의 구성에 관한 이론을 정리하기 쉬움. ( 2의 n 승 이런거 표현이 쉬움 )
• - 즉, 이진 트리는 2의 n 승으로 개수가 늘어나기 때문에 컴퓨터 내부에서 구현하기도 쉽고 효율적임.
• 모든 노드가 2개 이하의 자식 노드를 가지는 일반성을 가지고 있음.
• - 즉, 오른쪽, 왼쪽 이라는 방향 개념을 부여할 수도 있음.
• 오른쪽 노드와 왼쪽 노드의 개념적 접근(의미적 관계)도 있음 ( 이진 탐색 트리에서 힘을 갖게 된다? )

(2) 가득 찬 이진 트리 ( 포화 이진 트리 )

• 두번째에 해당하며, 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리를 의미함.
• 잎 노드가 채워질만큼 다 채워진 트리로 볼 수 있음. ( 최대 레벨 까지 노드가 다 채워져 있어야 함. )

(3) 완전 이진 트리

• 높이가 k인 이진트리가 0 레벨 부터 k-2 레벨 까지 다 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진 트리를 의미한다.
• 쉽게말해, 최대 레벨 바로전의 레벨의 노드들이 다 채워져 있어야 함.
• 또한, 최대 레벨의 노드가 왼쪽부터 차례로 채워지는 경우가 되어야 함.
• 즉, 최대 레벨의 노드가 1개만 존재해도 그건 완전 이진 트리로 볼 수 있음.
• 포화 이진 트리는 결과적으로 완전 이진 트리로도 볼 수 있음.

(4) 배열을 이용한 이진 트리의 구현

• 이진 트리를 구현하는 방법은 대표적으로 배열, 연결 리스트(포인터) 방식이 있음.
• 트리가 완전 이진 트리 또는 가득 찬 이진 트리인 경우 낭비되는 공간이 없어서 배열을 이용하면 효율적임.

• 하지만, 완전 이진 트리 또는 가득 찬 이진 트리가 아닌 이진 트리의 경우에는 위와 같은 모양이 될 수 있음.
• 이상태로 배열로 구현을 하게 되면, 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해지게 됨.
• 즉, 위와 같은 이진 트리 또는 일반적인 트리에서 배열로 구현을 하게 되면, 메모리 낭비가 심해질 수 있음.
• 결과적으로 트리나 이진 트리에서는 배열을 통해 구현하는 방식은 권장하지 않음.

(5) 포인터를 이용한 이진 트리의 구현

• 배열과 다르게 트리의 크기가 커질수록 메모리 낭비가 심해지지 않음. ( 단순히 노드를 만들어서 연결을 하면 됨. )
• 또한, 배열과 다르게 삽입과 삭제의 연산이 간단해짐.

• 위와 같은 연산을 통해서 이진 트리의 노드를 연결 리스트(포인터) 를 활용하여 생성 할 수 있음.
• 해당 J 노드는 루트 노드로 볼 수 있고, 구분은 왼쪽과 오른쪽으로 구분을 할 수 있음.

---

✅ 5. 이진 트리 연산

(1) 이진 트리의 순회

• 이진 트리의 각 노드를(빠짐없이 그리고 중복없이) 한 번씩 방문하는 행위를 의미함.

(2) 이진 트리의 순회 - 전위 순회

• 전위 순회: 루트노드 -> 왼쪽 자식노드(왼쪽 서브트리) -> 오른쪽 자식노드(오른쪽 서브트리)

• 왼쪽의 노드부터 한 번씩만 방문을 하게 됨. 

(3) 이진 트리의 순회 - 후위 순회

• 후위 순회: 왼쪽 자식노드(왼쪽 서브트리) -> 오른쪽 자식노드(오른쪽 서브트리) -> 루트노드

(4) 이진 트리의 순회 - 순회 단위 및 PLR, LPR, LRP

(5) 이진 트리 연산 - 순회 알고리즘

[ 전위 순회 PLR ]

void preorder(node* root) {
    if (root == NULL) return;       // 1️⃣ 종료 조건
    printf("%c ", root->data);      // 2️⃣ 현재 노드 출력
    preorder(root->left);           // 3️⃣ 왼쪽 서브트리 재귀 호출
    preorder(root->right);          // 4️⃣ 오른쪽 서브트리 재귀 호출
}

• 재귀호출 방식을 활용해서 순회 알고리즘을 구현할 수 있음.
• 처음 root 에는 트리의 루트 주소값이 들어가게 된다.
• 이후, root -> data 를 출력하고, preorder(root -> left); 를 통해 또 다시 자신의 함수를 호출하게 된다.
• 그렇게 되면, root -> left 즉, 해당 기존의 루트 주소값에 있는 left 주소값이 들어가게 된다.
• 그럼 해당 left의 데이터를 출력한 뒤 다시 preorder(root -> left) 를 호출하게 되는데, 이때 만약 잎 노드라 left가 존재하지 않는다면, left 를 호출하는 시점에서 조건문을 통해 root != NULL 임에 true 가 되어, return 이 된다.
• 이 return 이 되게 되면, 기존의 기존의 트리의 루트 노드로 이동을 하게 되면서 preorder(root -> right); 함수를 호출하게 된다.
• 그러면 right 의 주소값을 참조하게 되어, 그곳의 데이터를 출력하게 된다.
• 즉, left 노드의 주소값을 넣어서 보내기 전으로 돌아가게 된다. 그러면 left 노드의 주소값을 넣기 전인 기존의 노드주소를 가짐

[ 중위 순회 LRP ]

• 중위 순회 또한, 전위 순회와 비슷한 동작 원리로 재귀호출을 활용함.

[ 후위 순회 LPR ]

• 후위 순회 또한, 전위 순회와 비슷한 동작 원리로 재귀호출을 활용함.

(6) 이진 트리 연산 - 생성, 삽입, 삭제

• 생성: 일반적인 이진 트리를 생성하는 것은 연결 리스트 연산을 사용하며, 첫 노드를 생성하면 루트 노드가 됨.
• 삽입: 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용하며 삽입이 되게 됨.
• 삭제: 노드를 삭제할 때, 삭제하려는 노드가 잎 노드인 경우는 해당 노드를 가리키는 포인터를 NULL로 지정하면 됨.
• ( 잎 노드가 아닌 경우에는 삭제하려는 노드의 자식노드에 대한 처리를 추가로 해주어야 함. )
• ( 즉, 잎 노드가 아닌 내부 노드를 삭제하는 경우 잎 노드의 위치를 논리적으로 맞도록 다른 노드와 연결을 해줘야함 )

[ 노드 삽입 코드 ]

• node here: 삽입 할 노드의 부모 노드의 left 나 right 멤버 즉, 자식 노드의 포인터 값이 될 수 있음.
• node *it: 삽입 할 노드의 주소값
• here == NULL: 자식 노드의 포인터값이 null 인 경우에는 결국 잎 노드이기 때문에 바로 주소값을 연결해주면 됨.
• else: 하지만, null 이 아닌 경우에는 잎 노드가 아닌 내부 노드로 볼 수 있음.
• node* victim: 위의 else 즉, here 이 가리키는게 null 이 아닌 값이 존재하는 경우 해당 주소값을 복사하기 위한 용도
• victim = here: 기존의 here 주소값을 victim 에 넣음으로써, 복사가 된 상황임.
• *here = *it: here 주소값에 *it 주소값을 넣음으로써 기존의 참조하던 주소값은 날라간 상황임.
• return victim: 이후 victim 을 받아서 프로그램에서 올바르게 기존의 주소값을 연결하게 되는 로직임.

[ 노드 삭제 코드 ]

• node *root: 트리의 루트 노드 주소값
• node *it: 삭제하려는 노드의 주소값
• char direction: 삭제할 노드가 부모 기준으로 왼쪽인지 오른쪽 인지 알려주는 코드('l' , 'r')
• node *parent = searchParent(root, it): 삭제하려는 노드인 it 의 부모 노드를 찿는 함수이며, 반환값은 해당 it 노드의 부모 노드를 찾아서 주소값을 반환해준다. 그러면 결과적으로 *parent 에 해당 it 부모 노드의 주소값이 참조됨.
• if(parent == NULL): 만약 parent 가 NULL 인 경우 루트 노드거나, 찾지 못한 경우로 삭제 불가능하게 됨을 의미함.
• if(direction == 'l'): direaction 이 'l' 이면 parent 의 left 즉, 왼쪽 자식에 NULL 을 넣어 주소참조를 지움 즉, 삭제임.
• 결과적으로 'l' 과 'r' 둘 중 하나라도 아닌 경우에는 NULL 을 리턴함.

(7) 이진 트리 연산 - 이진 트리 노드 개수 세는 연산

• node *root: 함수를 호출하면서 root 노드 즉, 해당 root 의 주소값을 주게 됨.
• int num = 0: 해당 변수는 노드의 개수를 재귀호출 방식으로 구해서 저장을 해주는 변수임.
• if(root == NULL): root 노드가 NULL 인 경우에는 개수가 0이므로, 바로 return 을 하게됨.
• else: root 가 null 이 아닌 경우에는 여러개의 노드가 루트에 존재 할 수 있음. ( root 는 무조건 있는 경우임 )
• num = 1: root 가 존재할 경우에 else 에 들어가기 때문에 기본적으로 root 가 있다고 보며, num 을 1 올려줌.
• - 이후, 해당 함수를 재귀호출 하면서, root 의 left 와 right 를 확인 한 뒤 있으면 num 에 더해주는 식으로 구하게 됨.
• 결과적으로 이진트리의 개수를 세서 리턴을 해주는 알고리즘으로 볼 수 있음.

(7) 이진 트리 연산 - 이진 트리 잎 노드 개수 세는 연산

• 잎 노드만 구하는 연산은, 맨 마지막 노드로 가서 left 와 right 가 NULL 인 경우에 카운트를 1 올려주면 된다.

---

✅ 6. 일반 트리를 이진 트리로 변환

• 일반 트리를 이진 트리로 변환하는 경우가 은근히 많음.

(1) 이진 트리로 변환 방법

• (1) 일반 트리에 대하여 각 노드의 형제들을 연결
• (2) 각 노드에 대하여 가장 왼쪽 링크만 남기고 모두 제거
• (3) 루트 노드는 반드시 왼쪽 자식노드 하나만 갖도록 함
• 결과적으로 일반 트리를 이진 트리로 변환이 됨.