방송대 자료구조 7강 : 이진 트리의 표현과 순회

방송대 자료구조 7강: 이진 트리의 표현과 순회

같은 여덟 노드를 그려 놓고도 전위·중위·후위 순회의 출력은 모두 달라집니다. 차이는 노드가 아니라 루트를 언제 방문하느냐에 있습니다. 이 글은 트리의 가족 관계를 읽는 법부터 이진 트리의 배열·포인터 표현, 재귀 순회, 삽입·삭제·계수와 일반 트리 변환까지 연결하여, 그림을 보고 구조와 연산 결과를 스스로 추적하게 합니다.

노드가 같아도 관계와 방문 규칙이 바뀌면 결과가 달라진다

학습을 위해 다음 이진 트리를 가정하자. 루트는 8이고, 8의 왼쪽 자식은 3, 오른쪽 자식은 12다. 3의 자식은 1과 6, 6의 자식은 4와 7이며, 12의 오른쪽 자식은 15다. 값은 여덟 개뿐이지만 이 구조에서 답해야 할 질문은 여러 가지다.

6의 부모와 형제는 누구이며, 6을 루트로 하는 서브트리에는 무엇이 포함되는가?
루트의 레벨을 0으로 할 때 가장 깊은 노드의 레벨과 트리의 깊이는 얼마인가?
이 트리를 배열에 넣으면 각 노드의 인덱스는 어떻게 정해지는가?
루트를 왼쪽·오른쪽 서브트리보다 먼저, 사이, 나중에 방문하면 출력은 어떻게 달라지는가?

트리 학습의 핵심은 모양을 외우는 것이 아니다. 관계를 용어로 읽고, 관계를 저장 위치나 포인터로 표현하며, 방문 규칙을 재귀 호출 순서로 바꾸는 일이다. 이 세 층을 구분하면 같은 그림에서 용어·배열·코드 문제를 함께 풀 수 있다.

전체 지도: 먼저 부모·자식 관계를 확정하고, 다음으로 배열 또는 포인터 표현을 선택하며, 마지막으로 루트 방문 시점을 정한다. 순회 결과나 재귀식부터 외우면 구조가 조금만 달라져도 답을 잃기 쉽다.

트리는 한 출발점에서 아래로 갈라지는 논리적 계층이다

트리는 노드와 노드를 잇는 선으로 계층 관계를 표현하는 비선형 자료구조다. 강의에서는 직업을 예술가와 학자로, 다시 음악가·화가·과학자로 나누는 분류를 보여 준다. 상위 범주에서 하위 범주를 찾는 경로가 명확해 검색이 편리하고, 포함·분류·조직처럼 계급적 성격을 가진 자료를 표현하기 좋다.

노드는 트리에 저장되는 하나의 데이터 항목이다. 노드를 직접 잇는 선을 기준으로 위쪽 노드는 부모, 아래쪽 노드는 자식이다. 한 노드에서 부모 쪽으로 거슬러 올라가는 경로와 자식 쪽으로 내려가는 경로가 계층의 위치를 정한다.

용어	판정 기준	학습용 트리의 예
루트 노드	부모가 없는 최상위 노드	8
부모·자식	하나의 선으로 직접 연결된 위·아래 노드	3은 6의 부모, 6은 3의 자식
형제	같은 부모를 갖는 노드	1과 6, 4와 7
내부 노드	루트도 잎도 아닌 노드	3, 6, 12
잎 노드	자신의 서브트리를 갖지 않는 끝 노드	1, 4, 7, 15
서브트리	한 노드와 그 아래 후손으로 이루어진 트리	6을 루트로 하는 {6, 4, 7}

오개념 교정: 그림에서 옆에 놓였다고 형제가 되는 것은 아니다. 형제는 좌우 거리나 같은 레벨이 아니라 부모가 같은가로 판정한다. 1과 12는 레벨이 같지 않고, 3과 12는 같은 레벨이면서 부모 8도 같으므로 형제다.

차수·레벨·깊이는 선의 개수와 시작 기준을 먼저 확인한다

진입 차수는 노드로 들어오는 선의 수다. 루트는 부모가 없어 0이고, 강의의 일반적인 트리에서는 루트를 제외한 노드가 부모 하나와 연결되므로 1이다. 진출 차수는 노드에서 자식으로 나가는 선의 수다. 잎은 자식이 없어 0이고, 이진 트리의 모든 노드는 최대 2다.

노드의 레벨은 루트에서 해당 노드까지 이어진 경로의 길이다. 강의는 루트의 레벨을 0으로 둔다. 학습용 트리에서 8은 레벨 0, 3과 12는 레벨 1, 1·6·15는 레벨 2, 4와 7은 레벨 3이다. 트리의 깊이는 가장 큰 레벨에 1을 더하므로 3+1=4다.

질문	세는 대상	학습용 트리의 답
6의 진입 차수는?	6으로 들어오는 부모 연결	1
6의 진출 차수는?	6에서 자식으로 나가는 연결	2
15의 진출 차수는?	15의 자식 연결	0
7의 레벨은?	8→3→6→7의 선 세 개	3
트리의 깊이는?	최대 레벨 3에 1을 더함	4

교재마다 루트 레벨을 0 또는 1로 잡을 수 있으므로 숫자만 외우지 말고 기준을 먼저 확인해야 한다. 이 글과 강의에서는 루트 레벨 0, 깊이=최대 레벨+1을 일관되게 사용한다.

그림·중첩 집합·들여쓰기는 같은 포함 관계를 다르게 보여 준다

트리는 위에서 아래로 뻗는 그림뿐 아니라 중첩된 집합이나 들여쓰기로도 표현할 수 있다. 중첩 집합은 어떤 하위 집합이 어느 상위 집합 안에 들어가는지 강조하고, 들여쓰기는 텍스트만으로 레벨 차이를 드러낸다. 표현이 바뀌어도 부모·자식 관계와 루트에서 내려가는 경로는 변하지 않는다.

학습용 트리의 일부를 들여쓰기로 쓰면 다음과 같다. 같은 들여쓰기 깊이는 같은 레벨을 뜻할 수 있지만 형제 여부는 바로 위의 부모 항목을 함께 확인해야 한다.

이 표현에서 4와 7은 6 아래 같은 깊이에 있으므로 형제다. 1과 15도 같은 레벨이지만 각각 부모가 3과 12이므로 형제가 아니다. 들여쓰기를 읽을 때는 현재 항목보다 한 단계 덜 들여쓴 가장 가까운 위 항목을 부모로 찾는다.

추상 자료형은 트리에 무엇을 물을 수 있는지 명세한다

트리 추상 자료형의 객체는 루트 노드를 가진 유한 구조다. 배열 인덱스나 구조체 주소를 정하기 전에 트리를 만들고 바꾸고 탐색하는 연산의 의미를 정한다. 강의의 연산 15개는 역할에 따라 다음처럼 묶어 이해할 수 있다.

역할	연산	핵심 질문
생명 주기	`TreeCreate`, `Destroy`, `TreeCopy`	만들고 복사하고 메모리를 반환하는가?
구조 변경	`Insert`, `Delete`, `Replace`	노드 또는 값을 바꾼 뒤 관계를 보존하는가?
찾기·방문	`Search`, `Traverse`	특정 노드를 찾거나 모든 노드를 한 번씩 방문하는가?
관계 조회	`Root`, `Parent`, `Children`	루트·부모·자식을 돌려주는가?
상태 판정	`IsRoot`, `IsInternal`, `IsLeaf`, `IsEmpty`	노드의 역할이나 트리 공백 여부를 판정하는가?

Parent를 루트에 적용하거나 Children을 잎에 적용하면 요청한 관계가 존재하지 않으므로 오류 조건을 처리해야 한다. Delete는 노드를 없애는 것만으로 끝나지 않고 남은 노드의 계층을 다시 연결하는 재구성까지 포함할 수 있다.

이진 트리는 자식 수를 제한하고 왼쪽·오른쪽의 의미를 보존한다

이진 트리는 모든 노드의 차수가 2 이하인 트리다. 일반 트리와 달리 자식이 하나일 때도 그 자식이 왼쪽인지 오른쪽인지 구별한다. 따라서 왼쪽 자식 하나를 가진 트리와 오른쪽 자식 하나를 가진 트리는 모양뿐 아니라 의미적으로도 다른 이진 트리다.

이 제한은 단순해 보이지만 중요한 효과가 있다. 각 노드를 왼쪽 링크·데이터·오른쪽 링크의 고정된 구조로 표현할 수 있고, 전체 방문을 ‘현재 루트(P), 왼쪽 서브트리(L), 오른쪽 서브트리(R)’라는 세 단위의 순서로 설명할 수 있다.

가득 찬 이진 트리와 완전 이진 트리

가득 찬 이진 트리는 각 레벨에서 허용되는 최대 노드 수를 모두 가진다. 깊이가 4라면 레벨별 노드 수는 1, 2, 4, 8이고 전체는 15개다. 완전 이진 트리는 마지막 레벨 직전까지 모두 차 있으며, 마지막 레벨은 왼쪽부터 빈틈없이 채워진다.

판정 질문	가득 찬 이진 트리	완전 이진 트리
중간 레벨에 빈 자리인가?	허용하지 않음	허용하지 않음
마지막 레벨이 덜 찼는가?	허용하지 않음	허용함
마지막 레벨의 빈칸 위치는?	빈칸 자체가 없음	오른쪽 끝에만 생길 수 있음
배열 공간 사용	연속 인덱스를 빈틈없이 사용	연속 인덱스를 빈틈없이 사용

경계 사례: 마지막 레벨에 노드가 두 개뿐이어도 가장 왼쪽 자리부터 차 있으면 완전 이진 트리일 수 있다. 그러나 왼쪽 자리가 비고 오른쪽 자리에만 노드가 있으면 완전 이진 트리가 아니다. ‘모든 부모가 자식 둘을 가진다’는 기준은 가득 찬 트리 쪽에 가까우며 완전 트리의 정의가 아니다.

배열은 위치 공식을 얻고 포인터는 빈 자리를 저장하지 않는다

이진 트리를 배열로 표현할 때 루트를 인덱스 1에 두면, 인덱스 i인 노드의 왼쪽 자식은 2i, 오른쪽 자식은 2i+1에 둔다. 부모는 i를 2로 나눈 몫으로 찾는다. 완전 이진 트리와 가득 찬 이진 트리는 인덱스가 연속되므로 배열에 빈칸이 생기지 않는다.

반대로 한쪽으로 치우친 트리는 공간을 낭비한다. 루트에서 왼쪽 자식만 세 번 내려가면 사용 인덱스는 1→2→4→8이다. 노드는 네 개지만 인덱스 8까지 확보해야 하므로 사이의 3·5·6·7이 비게 된다. 깊어질수록 마지막 인덱스가 2의 거듭제곱으로 커지는 이유다.

포인터 표현은 각 노드에 왼쪽 자식 주소, 데이터, 오른쪽 자식 주소를 둔다. 없는 자식은 널 포인터로 표시하므로 기울어진 트리에서도 배열의 중간 빈칸을 예약하지 않는다.

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

표현 선택: 완전 트리처럼 위치가 촘촘하고 부모·자식 인덱스 계산이 중요하면 배열이 단순하다. 모양이 자주 바뀌거나 한쪽으로 기울어 빈 위치가 많다면 포인터가 공간과 구조 변경에 유리하다.

세 순회는 루트 방문 시점 하나로 구분한다

순회는 이진 트리의 모든 노드를 빠짐없이, 중복 없이 한 번씩 방문하는 연산이다. 현재 루트를 P, 왼쪽 서브트리를 L, 오른쪽 서브트리를 R이라고 두면 전위는 PLR, 중위는 LPR, 후위는 LRP다. 왼쪽이 오른쪽보다 먼저라는 규칙은 같고, P의 위치만 달라진다.

순회	재귀 단위	학습용 트리의 방문 결과
전위 순회	P→L→R	8, 3, 1, 6, 4, 7, 12, 15
중위 순회	L→P→R	1, 3, 4, 6, 7, 8, 12, 15
후위 순회	L→R→P	1, 4, 7, 6, 3, 15, 12, 8

중간 과정을 전위 순회로 확인해 보자. 먼저 8을 방문하고 왼쪽 서브트리의 루트 3을 방문한다. 3의 왼쪽 1을 처리한 뒤 3의 오른쪽 서브트리 6으로 가서 6→4→7을 방문한다. 왼쪽 전체가 끝난 다음에야 8의 오른쪽 12→15로 이동한다. ‘그림을 위에서 아래로 읽는다’가 아니라 각 서브트리에 같은 PLR 규칙을 다시 적용한다.

재귀 코드의 위치를 옮기면 방문 순서가 바뀐다

세 순회는 널 포인터에서 멈추는 조건과 왼쪽·오른쪽 재귀 호출은 같다. 현재 노드의 데이터를 처리하는 문장의 위치만 앞·가운데·뒤로 이동한다. 다음 코드는 강의의 재귀 구조를 학습용으로 정리한 C 예제다.

void preorder(const node *root) {
    if (root != NULL) {
        visit(root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void inorder(const node *root) {
    if (root != NULL) {
        inorder(root->left);
        visit(root->data);
        inorder(root->right);
    }
}

void postorder(const node *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        visit(root->data);
    }
}

root != NULL은 재귀가 빈 자식에서 끝나는 경계 조건이다. 이를 빼면 잎의 자식까지 내려간 뒤 존재하지 않는 노드의 필드에 접근하려 한다. 또한 중위 순회를 만들면서 함수 이름만 바꾸고 visit을 첫 줄에 그대로 두면 실제 동작은 여전히 전위 순회다.

삽입·삭제·계수는 바뀌지 않아야 할 연결부터 확인한다

포인터 이진 트리의 첫 노드는 루트가 된다. 이후 새 노드를 넣을 때는 목표 위치를 찾고, 새 노드의 왼쪽·오른쪽 링크를 정한 뒤 부모 링크를 새 노드에 연결한다. 기존 서브트리 사이에 삽입한다면 새 노드가 기존 서브트리를 먼저 이어받아야 연결이 끊기지 않는다.

잎 노드를 삭제할 때는 부모가 그 잎을 가리키던 링크를 널로 바꾸고 노드 메모리를 반환하면 된다. 그러나 내부 노드를 같은 방식으로 끊으면 그 아래 서브트리까지 접근할 수 없게 된다. 강의가 내부 노드 삭제에 자식 처리와 재구성이 추가로 필요하다고 강조하는 이유다.

노드 수와 잎 수는 순회하면서 부분 결과를 더한다. 빈 트리의 노드 수는 0, 비어 있지 않은 현재 노드는 1개이므로 전체 노드 수는 ‘1+왼쪽 노드 수+오른쪽 노드 수’다. 잎 수는 현재 노드의 두 자식이 모두 널일 때 1이고, 내부 노드에서는 두 서브트리의 잎 수를 더한다.

int count_nodes(const node *root) {
    if (root == NULL) return 0;
    return 1 + count_nodes(root->left)
             + count_nodes(root->right);
}

int count_leaves(const node *root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return count_leaves(root->left)
         + count_leaves(root->right);
}

학습용 트리에서 노드 수는 8이다. 잎 판정 조건을 적용하면 1·4·7·15만 두 자식이 모두 없으므로 잎 수는 4다. 12는 왼쪽 자식이 없어도 오른쪽 자식 15가 있으므로 잎이 아니다.

일반 트리는 왼쪽 자식·오른쪽 형제 규칙으로 이진화한다

자식 수가 제한되지 않은 일반 트리를 이진 트리로 바꿀 때는 형제를 옆으로 연결하고 각 부모의 가장 왼쪽 자식 링크만 남긴다. 변환된 이진 트리에서 왼쪽 링크는 첫 자식, 오른쪽 링크는 다음 형제를 뜻한다. 루트는 형제가 없으므로 오른쪽 링크를 갖지 않고 왼쪽 자식 하나만 가질 수 있다.

직접 구성한 예로 루트 A의 자식이 B·C·D이고, C의 자식이 E·F라고 하자. 이진화하면 A.left=B, B.right=C, C.right=D가 된다. C의 자식들은 C.left=E, E.right=F로 표현한다. B의 오른쪽에 C가 있다고 해서 C가 B의 자식이라는 뜻은 아니다. 변환 규칙에서 오른쪽 링크는 형제 관계를 나타낸다.

각 부모 아래의 형제들을 왼쪽에서 오른쪽 순서로 연결한다.
부모에서 자식으로 내려가는 링크는 가장 왼쪽 자식 하나만 남긴다.
변환 뒤 왼쪽 링크를 첫 자식, 오른쪽 링크를 다음 형제로 해석한다.
모든 원래 부모·자식과 형제 관계를 다시 따라가며 누락 여부를 검산한다.

잘못된 해석: 변환된 그림만 일반 이진 트리처럼 읽으면 오른쪽 형제를 오른쪽 자식으로 착각한다. 변환의 목적은 원래 관계를 잃지 않고 두 링크만으로 표현하는 것이므로, 링크 방향에 부여한 ‘첫 자식·다음 형제’ 의미를 함께 보존해야 한다.

새 트리 문제는 관계·표현·연산의 세 층으로 검산한다

처음 보는 트리 그림이나 코드가 나오면 다음 순서를 적용한다.

관계를 고정한다. 루트, 직접 부모·자식, 형제와 서브트리의 경계를 표시한다.
측정 기준을 적는다. 루트 레벨의 시작값, 차수의 방향, 깊이 정의를 문제와 맞춘다.
표현을 식별한다. 배열이면 인덱스 공식과 빈칸을, 포인터면 왼쪽·오른쪽 링크와 널을 본다.
방문 단위를 기호화한다. 전위 PLR, 중위 LPR, 후위 LRP 중 하나를 각 서브트리에 재귀적으로 적용한다.
변경 뒤 불변 관계를 확인한다. 삽입·삭제 뒤 후손이 유실되지 않았는지, 일반 트리 변환 뒤 형제 순서가 유지되는지 검사한다.

자가 점검으로 학습용 트리에서 6을 삭제한다고 생각해 보자. 6은 4와 7을 가진 내부 노드이므로 부모 3의 링크만 널로 바꾸면 두 잎을 함께 잃는다. 어떤 삭제 규칙으로 후손을 재배치할지 먼저 정해야 한다는 결론에 도달하면 관계와 연산을 함께 읽은 것이다.

핵심 개념 정리

관계: 루트는 부모가 없고, 잎은 진출 차수가 0이며, 형제는 같은 부모를 갖는다.
측정: 강의 기준에서 루트 레벨은 0이고 트리 깊이는 최대 레벨에 1을 더한 값이다.
이진 트리: 각 노드의 자식이 최대 둘이며 왼쪽·오른쪽 자식의 방향을 구별한다.
형태: 가득 찬 트리는 모든 자리가 차고, 완전 트리는 마지막 레벨만 덜 찰 수 있으며 왼쪽부터 채운다.
표현: 배열은 자식 인덱스를 빠르게 계산하고, 포인터는 기울어진 트리의 빈 배열 공간을 만들지 않는다.
순회: 전위·중위·후위는 각각 PLR·LPR·LRP이며 현재 루트 방문 시점으로 구별한다.
변경: 내부 노드 삭제는 후손 재연결이 필요하고, 일반 트리의 이진화에서는 왼쪽이 첫 자식, 오른쪽이 다음 형제다.

한 문장 전략: 트리를 만나면 선부터 따라 부모·자식 관계를 확정하고, 그 관계가 배열 인덱스인지 포인터 링크인지 해석한 다음, 루트를 언제 처리하는지 또는 변경 후 어떤 연결을 지켜야 하는지 순서대로 확인한다. 이 흐름은 다음 차시의 스레드 트리처럼 순회 효율을 바꾸는 구조를 배울 때도 기준점이 된다.

예상문제 10선

1. 트리에서 형제 노드를 판정하는 기준은?

① 같은 레벨에 있는가? ② 진출 차수가 같은가? ③ 같은 부모를 갖는가? ④ 그림에서 서로 이웃하는가?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

① 오답: 같은 레벨의 노드라도 부모가 서로 다르면 형제가 아니다.
② 오답: 자식 수가 같다는 사실은 계층상의 부모를 알려 주지 않는다.
③ 정답: 형제는 하나의 부모에서 직접 갈라져 나온 자식 노드들이다.
④ 오답: 그림 배치는 표현 방식일 뿐이며 직접 연결 관계를 대신할 수 없다.

2. 루트 노드와 잎 노드의 차이를 옳게 설명한 것은?

① 루트는 진입 차수가 0이고, 잎은 진출 차수가 0이다. ② 루트는 진출 차수가 0이고, 잎은 진입 차수가 0이다. ③ 루트와 잎은 모두 반드시 자식을 두 개 갖는다. ④ 루트는 부모가 하나이고, 잎은 부모를 갖지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

① 정답: 루트는 위에서 들어오는 부모 연결이 없고 잎은 아래로 나가는 자식 연결이 없다.
② 오답: 진입과 진출의 방향을 반대로 적용했다. 루트도 자식을 가질 수 있다.
③ 오답: 잎의 자식 수는 0이며 루트의 자식 수는 트리 모양에 따라 달라진다.
④ 오답: 부모가 없는 노드는 루트이고, 루트가 아닌 잎은 부모 하나를 갖는다.

3. 루트 레벨이 0이고 가장 깊은 잎의 레벨이 4인 트리의 깊이는?

① 3 ② 4 ③ 6 ④ 5

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

① 오답: 최대 레벨에서 1을 빼면 루트부터 잎까지의 층 수를 빠뜨린다.
② 오답: 4는 가장 깊은 노드의 레벨이며 강의가 정의한 트리 깊이가 아니다.
③ 오답: 최대 레벨에 2를 더한 값으로 깊이 정의보다 한 층 크게 계산했다.
④ 정답: 강의 기준에서 깊이는 최대 레벨+1이므로 4+1=5다.

4. 완전 이진 트리이지만 가득 찬 이진 트리는 아닌 경우는?

① 중간 레벨에 빈자리가 있고 그 아래에 노드가 있는 경우 ② 마지막 레벨이 왼쪽부터 일부만 채워진 경우 ③ 마지막 레벨의 오른쪽 노드만 있고 왼쪽 자리가 빈 경우 ④ 모든 레벨의 허용된 자리가 전부 채워진 경우

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

① 오답: 마지막 이전 레벨의 빈자리는 완전 이진 트리 조건을 어긴다.
② 정답: 완전 트리는 마지막 레벨이 덜 찰 수 있지만 왼쪽부터 연속되어야 한다.
③ 오답: 마지막 레벨도 왼쪽 빈자리보다 오른쪽 노드가 먼저 올 수 없다.
④ 오답: 모든 자리가 차면 완전 트리이면서 동시에 가득 찬 트리다.

5. 루트 인덱스가 1인 배열 이진 트리에서 인덱스 5 노드의 오른쪽 자식 인덱스는?

① 6 ② 9 ③ 10 ④ 11

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

① 오답: 현재 인덱스에 1만 더하는 방식은 이진 트리의 자식 위치 공식이 아니다.
② 오답: 2i-1을 적용한 값으로 오른쪽 자식 공식을 잘못 선택했다.
③ 오답: 2i=10은 왼쪽 자식의 인덱스다.
④ 정답: 오른쪽 자식은 2i+1이므로 2×5+1=11이다.

6. 루트 A, 왼쪽 자식 B, 오른쪽 자식 C인 이진 트리의 후위 순회 결과는?

① A, B, C ② B, A, C ③ B, C, A ④ C, B, A

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

① 오답: 루트를 먼저 처리하는 A-B-C는 전위 순회 PLR이다.
② 오답: 왼쪽과 루트 사이에 오른쪽을 방문하지 않은 B-A-C는 중위 순회다.
③ 정답: 후위 순회는 왼쪽 B, 오른쪽 C를 처리한 뒤 루트 A를 방문한다.
④ 오답: 후위 순회도 왼쪽 서브트리를 오른쪽보다 먼저 방문하므로 C가 앞설 수 없다.

7. 재귀적으로 전체 노드 수를 구하는 식으로 옳은 것은? 단, 빈 트리의 노드 수는 0이다.

① 1+왼쪽 서브트리 노드 수+오른쪽 서브트리 노드 수 ② 왼쪽 잎 수+오른쪽 잎 수 ③ 2×왼쪽 서브트리 노드 수 ④ 1+현재 노드의 진출 차수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

① 정답: 현재 노드 하나와 서로 겹치지 않는 두 서브트리의 노드 수를 모두 더한다.
② 오답: 잎만 더하면 자식을 가진 내부 노드와 현재 루트를 세지 못한다.
③ 오답: 왼쪽과 오른쪽 서브트리의 크기가 같다는 조건이 없어 두 배로 바꿀 수 없다.
④ 오답: 진출 차수는 직접 자식만 세므로 더 아래 후손을 포함하지 않는다.

8. 두 자식을 가진 내부 노드 X를 삭제하면서 부모의 X 링크를 널로만 바꿨다. 가장 직접적인 문제는?

① X가 자동으로 루트가 된다. ② X 아래 두 서브트리에 접근할 경로도 함께 끊긴다. ③ 모든 잎의 진입 차수가 2가 된다. ④ 트리의 모든 왼쪽·오른쪽 의미가 서로 바뀐다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

① 오답: 부모 링크를 끊는다고 삭제 대상이 새 루트로 연결되지는 않는다.
② 정답: 내부 노드는 후손의 진입 경로이므로 자식 재배치 없이 끊으면 서브트리가 유실된다.
③ 오답: 링크 단절은 잎의 부모 경로를 없앨 수 있지만 진입 차수를 2로 만들지 않는다.
④ 오답: 한 링크를 널로 바꾸는 일은 전체 트리의 방향을 자동 반전하지 않는다.

9. 일반 트리를 왼쪽 자식·오른쪽 형제 방식의 이진 트리로 바꾸는 절차로 옳은 것은?

① 모든 형제 링크를 지우고 부모의 가장 오른쪽 자식만 남긴다. ② 형제를 연결하고 부모의 가장 왼쪽 자식 링크만 남긴다. ③ 모든 자식을 부모의 오른쪽 링크 하나에 겹쳐 저장한다. ④ 형제 순서를 뒤집고 각 노드의 부모 링크를 왼쪽 링크로 사용한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

① 오답: 형제 연결을 없애면 둘째 이후 자식에 도달할 경로를 잃는다.
② 정답: 왼쪽 링크로 첫 자식에 들어가고 오른쪽 링크를 따라 다음 형제로 이동한다.
③ 오답: 하나의 포인터에 여러 주소를 겹칠 수 없고 형제 순서도 표현하지 못한다.
④ 오답: 강의의 변환은 원래 형제 순서를 보존하며 부모 포인터를 새로 두는 방식이 아니다.

10. 노드가 한쪽으로 길게 치우치고 삽입·삭제가 잦은 이진 트리의 표현과 검토 방법으로 가장 적절한 것은?

① 배열을 선택하고 빈 인덱스 수만 세면 연결 변경은 검토하지 않아도 된다. ② 배열과 포인터의 차이가 없으므로 루트 값만 보고 결정한다. ③ 포인터를 선택하되 삭제할 때 대상 링크만 끊고 후손은 무시한다. ④ 포인터를 선택하고 변경 전후의 부모·자식 링크와 후손 도달 경로를 검산한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

① 오답: 기울어진 트리는 배열 빈칸이 커지고 구조 변경도 인덱스만 세어서는 안전성을 확인할 수 없다.
② 오답: 트리 모양과 변경 빈도는 공간 사용과 링크 갱신 방식에 직접 영향을 준다.
③ 오답: 포인터 표현을 선택해도 내부 노드의 후손을 재연결하지 않으면 서브트리를 잃는다.
④ 정답: 포인터는 희소한 모양의 빈 배열 공간을 피하며, 변경 뒤 관계 검산이 후손 유실을 막는다.

참고 자료와 작성 기준

이 글은 한국방송통신대학교 자료구조 7강 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 강의의 트리 용어, 표현, 이진 트리와 순회 범위를 유지하면서 숫자 트리의 관계·인덱스·순회 추적, 재귀 코드 해설과 변환 검산 절차는 초급 학습자가 과정을 재현할 수 있도록 별도로 구성하고 확인했습니다.

작성·편집: 올에이클래스 학습연구팀
주요 근거: 한국방송통신대학교 자료구조 7강 「트리」 강의록 전체 60쪽
외부 보충 자료: 사용하지 않음
편집 원칙: 올에이클래스 편집 정책
최종 내용 검토: 2026-08-18

방송대 자료구조 7강 : 이진 트리의 표현과 순회