트리에 대한 문제풀이 내용이다.
트리(Tree)란?
- 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 유향 그래프이다. (비선형 자료구조)
- 부모가 없는 최상위 노드를 루트 노드라고 한다.
- 자식 노드가 2개 이상이며 최대 자식 노드가 n개인 트리를 n진 트리라고 부른다.
트리 형태의 자료구조는 일상에서도 자주 쓰이는데,
다항식의 수식을 계산하거나 검색창의 자동완성 기능이 이에 해당한다.
주로 데이터의 좌측과 우측에 자식 노드의 주소를 가리키는 연결 리스트를 이용해 이진 트리를 구현하는데,
연습문제와 함께 트리의 개념과 순회 방법을 익히고 일차원 배열 이진 트리(Binary Tree)를 구현해보자.
(배열의 인덱스 값과 이진 트리의 노드 값을 일치 시키고, 부모 노드 값 n 밑에 자식 노드의 값은 2n, 2n+1 이다.)
01. 다음 중 트리에 대해서 옳게 설명한 것이 아닌 것은?
(1) 모든 노드는 루트 노드에서 출발한다.
(2) 트리를 합하면 포리스트가 된다.
(3) 계층적인 구조를 갖고 있다.
(4) 선형구조를 나타내기에 알맞다.
02. 다음에서 트리구조로 나타내기에 적합하지 않은 것은?
(1) 가족의 계보 (2) 행렬
(3) 연산 수식 (4) 회사 종업원에 직급상의 상하 관계
04. 이진트리를 설명한 내용 중 잘못된 것은?
(1) 왼쪽 자식만 가진 이진트리와 오른쪽 자식만 가지는 이진트리는 서로 다르다.
(2) 탐색을 하기에 좋은 구조이다.
(3) 일반적인 이진트리는 배열로 저장시킬 수 없다.
(4) 포인터를 사용하여 노드들을 연결할 수 있다.
05. 이진트리(binary tree)에 대한 설명 중 잘못된 것은? 답이 없다.
(1) 최대 차수가(degree) 2이다.
(2) 이진트리의 노드의 개수는 0보다 크거나 같다.
(3) 이진트리에서 단말 노드의 수는 차수가 2인 비 단말 노드 수 +1이다.
(4) 레벨에서의 노드의 최대 개수는 2i-1개 이다.
06. 메모리상에 배열로 저장할 때 가장 낭비가 큰 트리는?
(1) 경사트리 (2) 이진트리
(3) 포화트리 (4) 완전트리
07. 다음 중 같은 개수의 노드가 저장되는 경우, 가장 높이가 작아지는 트리는?
(1) 경사트리 (2) 이진트리
(3) 포화트리 (4) 완전트리
08. 트리를 포인터를 이용하여 표현할 경우, 각 노드가 가져야 할 포인터의 수는?
(1) 트리의 차수만큼
(2) 각 노드는 각 레벨만큼
(3) 노드 수만큼
(4) 2개
09. 이진트리에서 높이가 5일 때, 이 트리는 최대 몇 개의 노드를 가질 수 있는가?
(1) 26개 (2) 8개
(3) 32개 (4) 31개
11. 이진트리가 링크 표현법으로 구현되었다고 할 때, 단말 노드의 조건으로 맞는 것은?
(1) node->left == NULL && node->right != NULL
(2) node->left != NULL && node->right == NULL
(3) node->left == NULL && node->right == NULL
(4) node->left != NULL && node->right != NULL
15. 다음의 이진트리에 대하여 다음 질문에 답하라.
(1) 루트 노드를 말하시오. 6
(2) 단말 노드의 집합과 비 단말 노드의 집합을 말하시오.
단말 노드 = {1,3,5,7,8,11}, 비 단말 노드 = {6,4,9,2,10}
(3) 노드 “4”의 자식 노드를 모두 말하시오. 2,5
(4) 노드 “2”의 형제 노드를 모두 말하시오. 5
(5) 노드 “9”의 후손 노드를 모두 말하시오. 7, 10, 8, 11
(6) 이 트리의 높이는? 4
16. 15번의 트리에 대하여 다음의 질문에 답하라.
(1) 위의 트리를 1차원 배열로 표현하시오.
(2) 위의 트리를 전위 순회한 결과를 쓰시오. 6 4 2 1 3 5 9 7 10 8 11
(3) 위의 트리를 후위 순회한 결과를 쓰시오. 1 3 2 5 4 7 8 11 10 9 6
(4) 위의 트리를 중위 순회한 결과를 쓰시오. 1 2 3 4 5 6 7 9 8 10 11
(5) 위의 트리를 레벨 순회한 결과를 쓰시오. 6 4 9 2 5 7 10 1 3 8 11
(6) 위의 트리는 이진 탐색 트리인가? 그 이유는?
이진탐색트리가 아니다. 이유는 8이 9의 오른쪽 서브 트리에 있기 때문이다.
17. 다음의 전위 순회와 중위 순회 결과를 생성할 수 있는 이진트리를 그리시오.
전위 순회 : A, B, D, E, C, F, G, H
중위 순회 : E, D, B, A, G, F, H, C
18. 정수 데이터가 이진 탐색 트리에 저장되어 있다. 이러한 이진 탐색 트리가 공백 상태로부터 다음과 같은 순서로 연산이 실행된다. 연산들에 의해 생성되는 이진 탐색 트리를 순서대로 그려라.
(1) 삽입 5, 7, 2, 8, 3 (2) 삭제 3
(3) 삽입 4, 3 (4) 삭제 7 (5) 삭제 5
19. 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색 트리를 생성하라.
5, 3, 7, 2, 4, 6, 9, 1, 8, 10
(1) 생성된 이진 탐색 트리에서 트리의 깊이, 비 단말 노드와 단말 노드의 집합을 쓰시오.
h = 4, 비 단말 노드 = {3, 5, 7, 9}, 단말 노드 = {1, 4, 6, 8, 10}
(2) 생성된 이진 탐색 트리를 중위 순회 했을 경우의 노드 방문 순서를 쓰시오.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(3) 생성된 이진 탐색 트리를 전위 순회 했을 경우의 노드 방문 순서를 쓰시오.
5, 3, 2, 1, 4, 7, 6, 9, 8, 10
(4) 생성된 이진 탐색 트리를 후위 순회 했을 경우의 노드 방문 순서를 쓰시오.
1, 2, 4, 3, 6, 8, 10, 9, 7, 5
(5) 생성된 이진 탐색 트리에서 8을 탐색 할 때 거치는 노드들을 나열하시오.
5, 7, 9, 8
(6) 이진 탐색 트리에서 특정한 값을 탐색 할 때 걸리는 시간은 어떤 값에 비례하는가?
일반적으로 탐색 연산은 생성된 트리의 높이에 비례 한다.
최악의 경우와 최선의 경우에 걸리는 시간을 O() 표기법으로 나타내라.
최악의 경우 : O(n) 평균의 경우 : O(log n) 최선의 경우 : O(1)
(7) 생성된 이진 탐색 트리를 1차원 배열을 이용하여 저장하여 보시오.
저장된 결과를 그리시오.
(8) 생성된 이진 탐색 트리를 1차원 배열을 이용하여 표현 하였을 경우,
부모노드의 위치와 왼쪽, 오른쪽 자식 노드의 위치는 어떻게 알 수 있는가?
부모노드 인덱스 = 자식노드인덱스/2
왼쪽 자식노드 인덱스 = 2*부모노드 인덱스
오른쪽 자식노드 인덱스 = 2*부모노드 인덱스 + 1
20. 다음의 데이터 값으로부터 만들어 질 수 있는 가장 높이가 낮은 이진 탐색 트리를 만드시오.
이 탐색 트리는 유일한 지를 말하시오. 1, 2, 3, 4, 5, 6 ,7 ,8 ,9 ,10
가장 낮은 h = 4 짜리인 이진 탐색 트리는 여러 개를 만들 수 있으므로 유일하지는 않다.
21. 다음의 데이터들이 어떤 식으로 이진 탐색 트리에 입력되었을 경우, 가장 균형 잡힌 이진 탐색 트리가 되는가? 10, 5, 6, 13, 15, 8, 14, 7, 12, 4
가장 균형 잡힌 이진 탐색 트리는 루트를 8이나 10으로 잡고 여러 개를 만들 수 있다.
25. 주어진 이진트리에서 자식이 하나만 있는 노드의 개수를 반환하는 함수를 작성하라.
Algorism]
one_node(x)
if x ≠ NULL
then if x->left ≠ NULL && x->right = NULL
then count++;
else if x->left = NULL && x->right ≠ NULL
then count++;
one_node(x->left);
one_node(x->right);
return count;
26. 주어진 이진트리에서 자식이 둘인 노드의 개수를 반환하는 함수를 작성하라.
Algorism]
two_node(x)
if x ≠ NULL
then if x->left ≠ NULL && x->right ≠ NULL
count++;
two_node(x->left);
two_node(x->right);
return count;
30. 이진 탐색 트리의 모든 노드의 값을 1씩 증가시키는 함수를 작성하여 보라.
Algorism]
data_increase(x)
if x ≠ NULL
then x->data++;
data_increase(x->left);
data_increase(x->right);
이진 트리 구현(C, ArrayList Tree)
#include <stdio.h>
#define MAX 100
typedef int element;
typedef struct {
element nodes[MAX];
} Tree;
void initialize(Tree *t){
int i;
for(i=0;i<MAX;i++)
t->nodes[i] = 0;
}
element search(Tree *t, int parent, element data){
if(data < t->nodes[parent])
search(t, 2*parent, data);
else if(data > t->nodes[parent])
search(t, 2*parent+1, data);
return parent;
}
void insertBinaryTree(Tree *t, int parent, element data){
if(t->nodes[parent] != 0){
if(data < t->nodes[parent])
insertBinaryTree(t, 2*parent, data);
else if(data > t->nodes[parent])
insertBinaryTree(t, 2*parent+1, data);
}
else
t->nodes[parent] = data;
}
int getTreeLength(Tree *t){
int i;
for(i=MAX-1;i>=0;i--)
if(t->nodes[i] != 0)
break;
return i;
}
void display(Tree *t){
int i;
int length = getTreeLength(t);
for(i=1;i<=length;i++)
printf("INDEX[%d] -> %d\n", i, t->nodes[i]);
}
void main(){
Tree t;
initialize(&t);
printf("Insert nodes : 8 4 2 1 6 5 7\n");
insertBinaryTree(&t, 1, 8);
insertBinaryTree(&t, 1, 4);
insertBinaryTree(&t, 1, 2);
insertBinaryTree(&t, 1, 1);
insertBinaryTree(&t, 1, 6);
insertBinaryTree(&t, 1, 5);
insertBinaryTree(&t, 1, 7);
display(&t);
}
이진 트리 구현(C, LinkedList Tree)
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
}TreeNode;
TreeNode *root = NULL;
TreeNode* createNode(element data){
TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
if(newNode == NULL)
return NULL;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void insert(TreeNode *t, element data){
if(root == NULL)
root = createNode(data);
else{
if(data < t->data){
if(t->left != NULL)
insert(t->left, data);
else
t->left = createNode(data);
}
else if(data > t->data){
if(t->right != NULL)
insert(t->right, data);
else
t->right = createNode(data);
}
}
}
void preorder(TreeNode *t){
if(t != NULL){
printf("%d ", t->data);
preorder(t->left);
preorder(t->right);
}
}
void inorder(TreeNode *t){
if(t != NULL){
inorder(t->left);
printf("%d ", t->data);
inorder(t->right);
}
}
void postorder(TreeNode *t){
if(t != NULL){
postorder(t->left);
postorder(t->right);
printf("%d ", t->data);
}
}
void main(){
insert(root,8);
insert(root,4);
insert(root,10);
insert(root,1);
insert(root,5);
insert(root,9);
printf("전위 순회:");
preorder(root);
printf("\n");
printf("중위 순회:");
inorder(root);
printf("\n");
printf("후위 순회:");
postorder(root);
printf("\n");
}
이진 트리 구현(C++, LinkedList Tree)
#include <iostream>
using namespace std;
typedef struct Tree{
int data;
struct Tree *left, *right;
} Tree;
void main(){
Tree *n1, *n2, *n3;
n1 = (Tree *)malloc(sizeof(Tree)); // 공간 할당
n2 = (Tree *)malloc(sizeof(Tree));
n3 = (Tree *)malloc(sizeof(Tree));
n1->data = 111;
n1->left = n2;
n1->right = n3;
n2->data = 222;
n2->left = NULL;
n2->right = NULL;
n3->data = 333;
n3->left = NULL;
n3->right = NULL;
cout << "n1->data = " << n1->data << endl;
cout << "n2->data = " << n2->data << endl;
cout << "n3->data = " << n3->data << endl;
cout << "n1->left->data = n2->data = " << n1->left->data << endl;
cout << "n1->right->data = n3->data = " << n1->right->data << endl;
}
'학습공간 > C, 자료구조와 알고리즘' 카테고리의 다른 글
| [7장] 연결 리스트 II (0) | 2019.11.23 |
|---|---|
| [6장] 연결 리스트 I (0) | 2019.11.23 |
| [5장] 큐 (0) | 2019.11.22 |
| [4장] 스택 (0) | 2019.11.22 |
| [3장] 배열, 구조체, 포인터 (0) | 2019.11.21 |
