다음 treetest() 함수로 만들어지는 트리의 유형은?typedef… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

다음 treetest() 함수로 만들어지는 트리의 유형은?
typedef struct treeNode {
    int data;
    struct treeNode *left, *right;
} treeNode;

void treetest() {
    treeNode n1 = { 12, NULL, NULL };
    treeNode n2 = { 33, NULL, NULL };
    treeNode n3 = { 21, &n1, &n2 };
    treeNode n4 = { 74, NULL, NULL };
    treeNode n5 = { 67, NULL, &n4 };
    treeNode n6 = { 59, NULL, &n5 };
    treeNode n7 = { 46, &n3, &n6 };
    treeNode* root = &n7;
}

스레드 이진 트리(threaded binary tree)

완전 이진 트리(complete binary tree)

이진 탐색 트리(binary search tree)

포화 이진 트리(full binary tree)

treetest()가 만드는 트리는 이진 탐색 트리이다.
루트 46의 왼쪽은 21(왼쪽 12, 오른쪽 33), 오른쪽은 59 → 67 → 74가 오른쪽 자식으로만 이어진다. 모든 노드에서 왼쪽 서브트리 < 노드 < 오른쪽 서브트리가 성립한다(12 < 21 < 33 < 46 < 59 < 67 < 74).
스레드 이진 트리: 빈 링크가 NULL 그대로이며 중위 선행자·후속자를 가리키는 스레드가 없다.
완전 이진 트리: 59에 왼쪽 자식이 없는데 더 아래 레벨에 노드가 있어 왼쪽부터 빈틈없이 채워지지 않았다.
포화 이진 트리: 노드가 7개지만 4개 레벨에 걸쳐 있어 모든 레벨이 꽉 차 있지 않다.