2. 이진 트리의 소개
- 이진 트리의 정의
이진 트리 (binary tree)
: 이진트리의 서브 트리들은 모두 이진트리여야 함
=> 트리 중에서 가장 많이 쓰이는 트리
이진 트리의 정의
- 공집합이거나
- 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의
이진 트리와 일반 트리의 차이점
- 이진 트리의 모든 노드는 차수가 2이하, 즉 자식 노드의 개수가 2이하지만 일반 트리는 자식 노드의 개수에 제한이 x
- 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있다
- 서브 트리간에 순서가 존재한다 (왼쪽 서브트리와 오른쪽 서브트리를 구별)
- 이진 트리의 성질
n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가짐
=> 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가짐
=>부모와 자식 간에는 정확하게 하나의 간선만이 존재
높이가 h인 이진 트리
노드의 최소 개수 : h개
노드의 최대 개수 : 2^h -1개
n개의 노드를 가지는 이진트리
최대 높이 : n
최소 높이 : log2(n+1)
- 이진 트리의 분류
- 포화 이진 트리 (full binary tree)
: 트리의 각 레벨에 노드가 꽉 차있는 이진 트리
- 완전 이진 트리 (complete binary tree)
: 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리
- 기타 이진 트리
*포화 이진 트리 => 완전 이진 트리 (역은 성립 x)
이진트리는 배열 또는 연결 리스트로 표현이 가능하다.
3. 이진 트리의 표현
- 배열(순차) 표현법
이진트리는 다음과 같은 속성 때문에 배열로 표현이 가능하다
- 루트 노드의 인덱스 i가 0인 경우
- 노드 i에 왼쪽 자식은 2*i+1 번째 노드이다.
- 노드 i에 오른쪽 자식은 2*i+2 번째 노드이다.
- 노드 i에 부모는 (i-1)/2 번째 노드이다.
- 루트 노드의 인덱스 i가 1인 경우
- 노드 i에 왼쪽 자식은 2*i 번째 노드이다.
- 노드 i에 오른쪽 자식은 2*i+1 번째 노드이다.
- 노드 i에 부모는 i/2 번째 노드이다.
배열로 표현한 완전이진트리
: 배열공간을 효율적으로 쓰고있다.
경사 이진 트리(skew tree) 인 경우
: 많은 공간이 낭비되고 있다.
배열을 사용하면 노드 접근이 빠르고 구현이 용이하다는 장점이 있지만,
편향 이진트리 같은 경우 많은 공간이 낭비될 수 있고 배열 크기 이상 노드를 추가할 수 없습니다.
- 연결 리스트 표현법
포인터를 사용하여 이진트리를 표현할 수 있다.
노드들이 가지고 있는 데이터가 정수라고 한다면 다음과 같이 표현할 수 있다.
struct BinaryTreeNode {
int data;
struct BinaryTreeNode *left
struct BinaryTreeNode *right
}연결 리스트는 배열보단 접근 속도가 느리지만 삽입 삭제가 쉽고 노드를 포인터로 연결하기 때문에 노드 수에 제한이 없다.
4 이진 트리의 순회
링크법으로 표현된 트리는 루트 노드를 가리키는 포인터만 있으면 트리 안의 모든 노드들에 접근할 수 있음
이진 트리 순회(traversal): 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미
이진 트리 순회 방법
이진 트리 순회 방법: 전위, 중위, 후위 3가지 방법 -> 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하냐에 따라 구분
- 전위 순회: 루트를 서브 트리에 앞서서 먼저 방문
- 중위 순회: 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문
- 후위 순회: 루트를 왼쪽과 오른쪽 서브 트리 방문 후에 방문
-> 루트 노드를 방문하는 작업을 V, 왼쪽 노드를 방문하는 작업을 L, 오른쪽 노드를 방문하는 작업을 R이라고 가정
전위 순회(preorder traversal): VLR
중위 순회(inorder traversal): LVR
후위 순회(postorder traversal): LRV
트리 순회 알고리즘은 순환 기법을 사용
-> 이진 트리에서 전체 트리나 서브 트리의 구조는 완전히 동일
-> 따라서, 전체 트리 순회에 사용된 알고리즘은 똑같이 서브 트리에 적용할 수 있음(다만 문제의 크기가 작아짐)
전위 순회
전위 순회: 루트를 먼저 방문하고 그 다음에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 마지막으로 방문
<알고리즘 7.4.1> 트리 전위 순회 알고리즘
preorder(x)
if x != NULL
then print x->data; // 1. 루트 노드 방문
preorder(x->left); // 2. 왼쪽 서브 트리 방문
preorder(x->right); // 3. 오른쪽 서브 트리 방문
1. 노드 x가 NULL이면 더 이상 순환 호출을 하지 않음
2. x의 데이터를 출력
3. x의 왼쪽 서브 트리를 순환 호출하여 방문
4. x의 오른쪽 서브 트리를 순환 호출하여 방문중위 순회
중위 순회: 먼저 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순으로 방문
<알고리즘 7.4.2> 트리 중위 순회 알고리즘
inorder(x)
if x != NULL
then inorder(x->left); // 1. 왼쪽 서브 트리 방문
print x->data; // 2. 루트 노드 방문
inorder(x->right); // 3. 오른쪽 서브 트리 방문
1. 노드 x가 NULL이면 더 이상 순환 호출을 하지 않음
2. x의 왼쪽 서브 트리를 순환 호출하여 방문
3. x의 데이터를 출력
4. x의 오른쪽 서브 트리를 순환 호출하여 방문후위 순회
후위 순회: 먼저 왼쪽 서브 트리, 오른쪽 서브 트리, 루트 순으로 방문
<알고리즘 7.4.3> 트리 후위 순회 알고리즘
postorder(x)
if x != NULL
then postorder(x->left); // 1. 왼쪽 서브 트리 방문
postorder(x->right); // 2. 오른쪽 서브 트리 방문
print x->data; // 3. 루트 노드 방문
1. 노드 x가 NULL이면 더 이상 순환 호출을 하지 않음
2. x의 왼쪽 서브 트리를 순환 호출하여 방문
3. x의 오른쪽 서브 트리를 순환 호출하여 방문
4. x의 데이터를 출력전위, 중위, 후위 순회의 선택 방법
- 트리를 이용해서 문제를 해결할 때 트리의 순회 알고리즘만 가지고도 해결되는 경우가 많음
- 순서가 중요하지 않고 노드를 전부 방문하기만하면 되는 경우에 어떤 순회 방법을 사용해도 상관 없음
전위, 중위, 후위 순회 구현
<프로그램 7.4.1> 이진 트리의 3가지 순회 방법
// 전위 순회
void preorder(TreeNode *root){ // 매개변수: 루트를 가리키는 포인터
if(root){
printf("%d ",root->data); // 노드 방문
preorder(root->left); // 왼쪽 서브 트리 순회
preorder(root->right); // 오른쪽 서브 트리 순회
}
}
// 중위 순회
void inorder(TreeNode *root){
if(root){
inorder(root->left); // 왼쪽 서브 트리 순회
printf("%d ",root->data); // 노드 방문
inorder(root->right); // 오른쪽 서브 트리 순회
}
}
// 후위 순회
void postorder(TreeNode *root){
if(root){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}순회 프로그램
<프로그램 7.4.2> 링크 표현법으로 생성된 이진 트리의 순회
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
}TreeNode;
// 15
// 4 20
// 1 16 25
TreeNode n1={1,NULL,NULL};
TreeNode n2={4,&n1,NULL};
TreeNode n3={16,NULL,NULL};
TreeNode n4={25,NULL,NULL};
TreeNode n5={20,&n3,&n4};
TreeNode n6={15,&n2,&n5};
TreeNode *root = &n6;
// preorder, inorder, postorder 함수를 여기에 삽입
//...
// 주 함수
int main(){
printf("preorder: ");
preorder(root);
printf("\n");
printf("inorder: ");
inorder(root);
printf("\n");
printf("postorder: ");
postorder(root);
printf("\n");
return 0;
}
레벨 순회
레벨 순회(level order): 각 노드를 레벨 순으로 검사하는 순회 방법
- 루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨 증가
- 동일한 레벨의 경우에는 좌에서 우로 방문
- 순회법이 스택을 사용했던 것에 비해 레벨 순회는 큐를 사용하는 순회법
- 코드에는 스택이 나타나지 않았지만 순화 호출을 하였기 때문에 간접적으로 스택을 사용한 것
- 큐에 있는 노드를 꺼내어 방문
- 그 노드의 자식 노드를 큐에 삽입하는 것으로 한 번의 반복을 끝냄
- 이러한 반복을 큐에 더 이상의 노드가 없을 때까지 계속함
<알고리즘 7.4.4>
level_order(root)
initialize queue;
if(root = NULL) then return;
enqueue(queue, root);
while is_empty(queue) != TRUE do
x <- dequeue(queue);
print x <- data
if(x->left != NULL) then
enqueue(queue,x->left);
if(x->right != NULL) then
enqueue(queue, x->right);
큐를 초기화
트리 root가 NULL이면 종료
트리 root의 루트 노드를 큐에 삽입
큐가 공백 상태가 될 때까지 계속 다음을 반복
큐의 맨 처음에 있는 노드를 x로 가져옴
x의 데이터 값 출력
x의 왼쪽 자식이 NULL이 아니면 큐에 삽입
x의 오른쪽 자식이 NULL이 아니면 큐에 삽입<프로그램 7.4.3> 레벨 순회 프로그램
typedef TreeNode * element;
// 큐의 소스를 여기에
// ...
// 레벨 순회
void level_order(TreeNode*ptr){
QueueType q;
init(&q);
if(ptr != NULL) return;
enqueue(&q,ptr);
while(!is_empty(&q)){
ptr = dequeue(&q);
printf("%d",ptr->data);
if(ptr->left){
enqueue(&q,ptr->left);
}
if(ptr->right){
enqueue(&q,ptr->right);
}
}
}이진 트리 순회의 응용: 수식 트리 처리
수식 트리(expression tree): 산술식이나 논리식의 연산자와 피연산자들로부터 만들어짐, 피연산자는 단말 노드가 되며, 연산자는 비단말 노드가 됨
-> 가장 적합한 순회 방법은 자식 노드를 먼저 방문하는 후위 순회
수식a+ba-(b*c)(a<b)or(c<d)
| 전위 순회 | +ab | -a*bc | or<ab<cd |
| 중위 순회 | a+b | a-(b*c) | (a<b)or(c<d) |
| 후위 순회 | ab+ | abc*- | ab<cd<or |
<알고리즘 7.4.5> 수식 트리 계산 프로그램
evaluate(exp)
if exp = NULL
then return 0;
if exp->left = NULL and exp->right = NULL
then return exp->data;
x <- evaluate(exp->left);
y <- evaluate(exp->right);
op <- exp.data;
return (x op y);
만약 자식 노드들이 없으면 데이터 필드 값을 반환
왼쪽 서브 트리에 대하여 evaluate를 순환 호출
오른쪽 서브 트리에 대하여 evaluate를 순환 호출
데이터 필드에서 연산자를 추출
추출된 연산자를 가지고 연산을 수행해서 결과 값을 반환<프로그램 7.4.4> 수식 트리 계산 프로그램
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// +
// * +
// 1 4 16 25
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, NULL, NULL };
TreeNode n3 = { '*', &n1, &n2 };
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4, &n5 };
TreeNode n7 = { '+', &n3, &n6 };
TreeNode *exp = &n7;
// 수식 계산 함수
int evaluate(TreeNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return root->data;
else { // 후위 순회 방법 이용
int op1 = evaluate(root->left);
int op2 = evaluate(root->right);
switch (root->data) {
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
}
return 0;
}
int main()
{
printf("%d", evaluate(exp));
}
이진 트리 순회의 응용: 디렉터리 용량 계산
-> 후위 순회를 사용하되 순환 호출되는 순회 함수가 용량을 반환하도록 만들어야 함
<프로그램 7.4.5> 디렉터리 용량 계산 프로그램
int calc_direc_size(TreeNode *root){
int left_size, right_size;
if(root !=NULL){
left_size = calc_direc_size(root->left);
right_size = calc_direc_size(root->right);
return (root->data+left_size+right_size);
}
return 0;
}
int main(){
TreeNode n4={500,NULL,NULL};
TreeNode n5={200,NULL,NULL};
TreeNode n3={100,&n4,&n5};
TreeNode n2={50,NULL,NULL};
TreeNode n1={0,&n2,&n3};
printf("Directory Size=%d\n",calc_direc_size(&n1));
return 0;
}
5 이진 트리의 연산
노드의 개수
- 노드의 개수 계산: 트리 안의 노드들을 전체적으로 순회해야 함, 각각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환하면 됨
<알고리즘 7.5.1> 이진 트리에서 노드 개수 구하는 알고리즘
get_count(x)
if x != NULL then
return 1+get_count(x->left)+get_count(x->right);
int get_node_count(TreeNode *node){
int count = 0;
if(node != NULL){
count = 1 + get_node_count(node->left) + get_node_count(node->right);
}
return count;
}단말 노드 개수 구하기
- 단말 노드의 개수 계산: 트리 안의 노드들을 전체적으로 순회해야 함, 순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 0이 되면 단말 노드이므로 1을 반환, 그렇지 않으면 비단말 노드이므로 각각의 서브 트리에 대하여 순환 호출한 다음 반환되는 값을 서로 더하면 됨
<알고리즘 7.5.2> 이진 트리에서 단말 노드 개수 구하는 알고리즘
get_leaf(T)
if T != NULL then
if T->left = NULL and T->right = NULL
then return 1;
else return get_leaf(T->left) + get_leaf(T->right);
int get_leaf_count(TreeNode *node){
int count;
if(node != NULL){
if(node->left == NULL && node->right == NULL){
return 1;
}else{
count = get_leaf_count(node->left) + get_leaf_count(node->right);
}
}
return count;
}높이 구하기
- 높이 계산: 각 서브 트리에 대하여 순환 호출해야 함. 순환 호출이 끝나면 각각 서브 트리로부터 서브 트리의 높이가 반환되는데 그 중 최대값을 구하여 반환해야 함
<알고리즘 7.5.3> 이진 트리에서 높이 구하는 알고리즘
get_height(T)
if T != NULL then
return 1 + max(get_height(T->left), get_height(T->right));
int get_height(TreeNode *node){
int height = 0;
if(node != NULL){
height = 1 + max(get_height(node->left), get_height(node->right));
}
return height;
}Quiz
- 이진트리에서 비단말 노드의 개수를 계산하는 함수 get_nonleaf_count(TreeNode*t)를 작성하시오
int get_nonleaf_count(Treenode *node){
return get_node_count(node) - get_leaf_count(node);
}- 두 개의 트리가 같은 구조를 가지고 있고, 대응되는 노드들이 같은 데이터를 가지고 있는지를 검사하는 함수를 equal(TreeNode*t1,TreeNode*t2)를 작성해보자. 여기서 t1, t2는 트리의 루트 노드를 가리키는 포인터임
int equal(TreeNode* t1, TreeNode* t2){
int ret = false;
if(t1 == NULL && t2 == NULL) ret = true;
else if(t1 != null && t2 != null && (t1->data == t2->data) && equal(t1->left, t2->left) && equal(t1->right,t2->right)){
ret = true;
}
return ret;
}
int equal(TreeNode *first, TreeNode *second){
return ((!first && !second) || (first && second &&
(first->data == second->data) &&
equal(first->left, second->left) &&
equal(first->right, second->right)));
}6 스레드 이진 트리
- 트리의 노드의 개수가 n개면, 링크의 개수는 2n개(각 노드당 2개의 링크가 있으므로)
- 링크 중에서 n-1개의 링크들이 루트 노드를 제외한 n-1개의 노드를 가리킴. 따라서 2n개 중에서 n-1개는 NULL 링크가 아니지만 나머지 n+1개의 링크는 NULL임을 알 수 있음.
- 따라서, NULL 링크를 이용하여 순환 호출 없이 트리의 노드들을 순회할 수 있는지 생각해볼 수 있음
- NULL 링크에 중위 순회 시에 선행 노드인 중위 선행자(inorder predecessor)나 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리가 스레드 이진 트리(threaded binary tree) -> 스레드(thread) 즉, 실을 이용하여 노드들을 순회 순서대로 연결 시켜놓은 트리
문제를 단순화 하기위해 중위 후속자만 저장
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
int is_thread; // 만약 오른쪽 링크가 쓰레드라면 true -> 태그 필드
}TreeNode;- NULL 링크에 쓰레드가 저장되면 링크에 자식을 가리키는 포인터가 저장되어 있는지 아니면 스레드가 저장되어 있는지가 구분되지 않음, 따라서 구분해주는 태크 필드가 필요
- is_thread가 true이면 right은 중위 후속자이고, is_thread가 false이면 오른쪽 자식을 가리키는 포인터가 됨
// 노드 p의 중위 후속자를 반환하는 함수
TreeNode *find_successor(TreeNode *p){
// q는 p의 오른쪽 포인터
TreeNode *q = p->right;
// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
if(q == NULL || p->is_thread == true){
return q;
}
// 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
while(q->left != NULL) q = q->left;
return q;
}
// 스레드 이진 트리에서 중위 순회를 하는 함수
// 중위 순회는 가장 왼쪽 노드부터 시작하기 때문에, 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동
void thread_inorder(TreeNode *t){
TreeNode *q;
q = t;
while(q->left != NULL) q = q->left; // 가장 왼쪽 노드로 감
do{
printf("%c",q->data); // 데이터 출력
q = find_successor(q); // 후속자 함수 호출
}while(q != null); // null이 아니면
}프로그램 <7.6.1> 스레드 이진 트리 순회 프로그램
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
int is_thread; // 스레드이면 true
} TreeNode;
// G
// C F
// A B D E
TreeNode n1 = { 'A', NULL, NULL, 1 };
TreeNode n2 = { 'B', NULL, NULL, 1 };
TreeNode n3 = { 'C', &n1, &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1 };
TreeNode n5 = { 'E', NULL, NULL, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode* exp = &n7;
TreeNode* find_successor(TreeNode* p)
{
TreeNode* q = p->right;
if (q == NULL || p->is_thread == true) {
return q;
}
while (q->left != NULL)
q = q->left;
return q;
}
void thread_inorder(TreeNode* t)
{
TreeNode* q = t;
while (q->left != NULL)
q = q->left;
do {
printf("%c ", q->data);
q = find_successor(q);
} while (q != NULL);
}
int main()
{
// 스레드 설정
n1.right = &n3; // A -> C
n2.right = &n7; // B -> G
n4.right = &n6; // D -> F
// 중위 순회
thread_inorder(exp);
}
Quiz
- 이진 트리의 노드의 개수가 n개라면 NULL 링크의 개수? -> n+1개
- 스레드 이진 트리에서 NULL 링크 필드에 저장되는 것은 무엇인가? -> 중위 후속자
'자료구조와 알고리즘 ft. 수업 > 알고리즘 정리' 카테고리의 다른 글
| Array (배열) (0) | 2023.04.09 |
|---|---|
| array, search, insert, delete (0) | 2023.04.07 |
| 1. 트리 (0) | 2023.03.07 |
| 3. 덱 (deque) (0) | 2023.03.07 |
| 2. 큐의 구현 (0) | 2023.03.07 |