자료구조: CHAP 8 트리(1)
2021. 5. 24
순천향대학교 컴퓨터공학과
목차
트리, 이진 트리의 개념
이진 트리 표현
이진 트리 순회
이진 트리의 성질
이진트리 응용: 수식 트리
트리 연산
스레드 이진트리
이진탐색트리
트리(TREE)
리스트, 스택, 큐 등은 선형 구조
트리: 계층적인 구조를 나타내는 자료구조
트리
트리(tree)란?
계층적 구조를 나타내는 자료구조
부모-자식 관계의 노드들로 구성
트리
트리 응용 분야
계층적인 조직 표현
파일 시스템
인공지능의 결정트리(decision tree) 등
대표이사
총무부 영업부 생산부
트리 정의
형식적 정의
한 개 이상의 노드들로 구성
루트(root)라는 특정 노드 존재 (부모가 없는 노드)
나머지 노드들은 T1, T2, …, Tn으로 분할
T1, T2, …, Tn은 루트의 서브 트리라 한다. (재귀적 정의)
각 서브 트리는 disjoint 집합
T1
T2
T3
트리 용어
루트(root): 부모가 없는 노드
서브 트리(subtree):
간선(edge):노드간의 연결 선
단말 노드 또는 잎노드(terminal/leaf): 차수가 0인 노드
비 단말노드(non terminal): 단말 노드 이외의 노드들
자식 노드(child node): 노드 X의 서브 트리의 루트들은 X
A
B C D
E F G H I J
트리 용어(2)
조상 노드(ancestor node): 루트부터 노드에 이르는 경로 상의 모든 노드들
자손 노드(descendent node): 서브 트리상의 모든 노드들
노드의 차수(degree): 서브 트리의 개수
트리의 차수: 트리에 속한 노드의 최대 차수
수준(level): 트리의 각 층에 매겨지는 번호, 루트의 레 벨은 1, 한 층씩 내려갈수록 1씩 증가
높이(height) 또는 깊이(depth): 트리에 속한 노드의 최
A
B C D
E F G H I J
트리 표현
일반적으로 트리를 리스트로 표현
노드의 차수에 따라 링크 수가 다름
노드 크기가 일정하지 않으면 복잡함
B
A
D
E F
C
G
A
B C D
F
E G
이진 트리
이진 트리(binary tree)의 정의
공집합이거나
루트와 왼쪽 서브트리와 오른쪽 서브트리로 구성 되며, 각 서브트리는 이진트리이다. (순환적 정 의에 유의)
이진 트리와 일반 트리간의 차이점
자식 노드 개수의 제한성
공백 유무
서브트리간에 순서 존재 여부
예제
이진 트리 예
루트 노드?
잎 노드?
중간 노드?
차수가 1인 노드는?
트리 높이?
트리 차수?
B
A
C
D E F G
H I
편향 이진트리
왼편 또는 오른편으로 편향되어 있는 트리
(skewed binary tree)
이진트리의 특징
n개 노드를 가진 이진 트리가 갖는 간선의 개수는?
B
A
C
D E F G
이진트리의 특징 (2)
높이가 h인 이진 트리는
최소 몇 개의 노드를 갖는가?
최대 몇 개의 노드를 갖는가?
B
A
C
D E F G
이진 트리의 특징 (3)
N개의 노드를 갖는 이진 트리의 높이는?
최대 높이는?
최소 높이는?
B
A
C
D E F G
이진 트리의 종류
포화 이진트리(full binary tree)
각 트리 수준에 노드가 꽉 차 있는 이진트리
트리 수준 단위로 왼쪽부터 오른쪽의 순서로 번 호 부여
완전 이진트리(complete binary tree)
트리 높이가 k일 때, 수준 1부터 k-1까지 노드가 모두 채워지고,
마지막 수준 k에서, 왼쪽부터 오른쪽의 순서로 노드가 채워지는 이진트리
예제
이진트리의 표현
배열 표현
링크 이용
배열 표현
예제: 배열 표현
배열 표현 (2)
부모와 자식노드 간의 인덱스 관계
노드의 인덱스가 i일 때,
부모 노드 인덱스:
왼쪽 자식 노드 인덱스:
오른쪽 자식 노드 인덱스:
링크 이용
트리에서 노드를 구조체로 표현하고 , 각 노드 의 링크가 자식 노드를 가리키게 하는 방법
노드의 구조체 표현
typedef struct TreeNode { int data;
데이터
왼쪽 자식노드 오른쪽 자식노드
예제: 링크 이용
이진트리 순회
이진트리 순회(traversal)란?
트리에 포함된 모든 노드를 방문하는 것
이진트리 순회 방법은 루트, 왼쪽 서브트리, 오른쪽 서브트리 중에서 루트를 언제 방문하는 가에 따라서 구분
전위(preorder)
중위(inorder)
후위(postorder)
전위 순회
전위 순회(preorder traversal)는 다음의 순 서로 노드를 방문.
루트 노드 방문
왼쪽 서브트리 방문
오른쪽 서브트리 방문
다음 트리를 전위 순회하면?
B
A
C
D E F G
H I
전위 순회 알고리즘
알고리즘 (순환적)
B
A
C
D E F G
H I
preorder(T) {
}
중위 순회
중위 순회(inorder traversal)는 다음의 순 서로 노드를 방문.
왼쪽 서브트리 방문
루트 노드 방문
오른쪽 서브트리 방문
다음 트리를 중위 순회하면?
B
A
C
D E F G
H I
중위 순회 알고리즘
B
A
C
D E F G
H I
inorder(T) {
}
후위 순회
후위 순회(postorder traversal)는 다음의 순 서로 노드를 방문.
왼쪽 서브트리 방문
오른쪽 서브트리 방문
루트 노드 방문
다음 트리를 후위 순회하면?
B
A
C
D E F G
H I
후위 순회 알고리즘
B
A
C
D E F G
H I
postorder(T) {
}
트리 순회 반복적 버전
트리 순회의 반복적 버전은 스택을 이용
중위 순회 고려
B
A
C
D E F G
중위 순회 반복적 버전 (분석)
void inorder_iter(TreeNode *root) { // 스택 이용
TreeNode* curr = root;
1. currr가 NULL이 아니면 curr 기준으로 트리의
가장 왼쪽 노드에 이를 때까지 노드를 스택에 저장 2. 스택에서 노드 node를 가져와서 출력
3. curr <- node->right 4. 위의 과정을 반복 }
}
B
A
C
D E F G
중위 순회 반복적 버전 알고리즘
void inorder_iter(TreeNode *root) { // 스택 이용
TreeNode* curr = root;
while (curr != NULL || !is_empty(s)) {
while (curr != NULL) {//가장 왼쪽 노드까지 push(&s, curr);
curr = curr->left;
}
curr = pop(&s);
print(curr);
// curr과 좌측 서브트리는 방문 상태 // 이제 우측 서브트리를 방문할 순서
B
A
C
트리 수준별 순회
트리의 수준별 순회(level order)란?
트리의 낮은 수준부터 높은 수준의 순서로 방문 하되, 같은 수준에 있는 노드들을 좌측에서 우측 의 순서로 모두 방문하는 순회
다음 트리를 수준별로 순회하면?
B
A
C
D E F G
예제: 트리 수준별 순회
큐를 이용
트리 수준별 순회 알고리즘
level_order(T) {
initQueue(q); // 큐 q 초기화
if (T != NULL) then enqueue(q, T);
}
//NULL은 큐에 삽입하지 않는다.
B
A
C
D E F G
후위 순회 응용
자식을 먼저 처리하고, 부모 노드를 처리해 야 할 경우에 선택
예: 디렉토리 용량 계산, 수식 트리 계산 등
이진 트리 응용
수식 트리
디렉토리 용량 계산
수식 트리
수식 트리(expression tree)
산술식, 논리식의 연산자와 피연산자로 트리를 구성
피연산자는 잎노드에, 연산자는 비단말노드에 위치
왼쪽 서브트리는 왼쪽 피연산자를, 오른쪽 서브트리 는 오른쪽 피연산자를 표현
수식 트리 표현 및 평가
다음 수식 트리를 평가하라.
/
typedef union {
int operand;
char operator;
} element;
