#트리
hierachical-계층적 구조(스택, 큐, 리스트 등은 linear-선형구조)
node: 트리 구성 요소
link = edge: 간선
root: 부모가 없는 노드
subtree: 한 노드와 그 노드들의 자손들로 이루어진 트리 *빈 트리 역시 서브트리(공집합과 연관지어 생각)
단말 노드 = leaf node = terminal node: 자식이 없는 노드
비단말 노드 = non-leaf node = non-terminal node: 자식이 하나라도 있는 노드
레벨: 트리 각 층 번호
높이: 트리의 최대 레벨
차수 = degree: 노드가 가지고 있는 자식 노드 개수
-일반 트리
-이진 트리 = binary-tree: 모든 노드가 자식이 없거나 2개의 서브 트리를 가진다. (즉, 차수가 0, 1, 2일 수 있음. 1개도 가능한 이유 = 공집합 또한 서브트리이므로)
당연히 이진 트리의 서브 트리 모두 이진 트리.
서브 트리 간의 순서가 존재.
-이진 트리 성질
1. 노드 개수가 n개이면 간선 개수 n-1개 - root 제외 모든 노드가 1개의 간선을 가짐
2. 높이가 h일 때 노드 개수 최소 h, 최대 2^(h)-1
3. n개 노드를 가지는 이진트리 높이 최대 n, 최소 log(n+1)(+올림연산 활용) ->2번 성질로부터 도출 가능
포화 이진 트리 = full binary tree: 모든 레벨의 노드가 꽉 차있는 이진트리(모든 노드가 자식 2개씩)-> 높이가 h일 때 포화 이진 트리 노드 개수=2^(h)-1
완전 이진 트리 = complete binary tree: 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 트리. 즉, 포화 이진 트리와 다르게 마지막 레벨에는 노드 몇개가 비어있는 것이 가능하나, 맨 왼쪽부터 가장 오른쪽에 있는 노드 사이에 비어있는 곳이 없어야)
-이진 트리 표현 방식
배열표현: 모든 이진트리를 포화 이진 트리로 가정(각 노드에 번호를 부여하기 위해), 부여된 번호와 일치하는 인덱스 자리에 데이터를 넣는 방식.
부모-자식 인덱스 관계
노드 i의 부모 노드 인덱스=i/2,
노드 i의 왼쪽 자식 노드 인덱스=2i
노드 i의 오른쪽 자식 노드 인덱스=2i+1
->부모의 인덱스를 알면 자식의 인덱스를 알 수 있음, 또한 자식의 인덱스를 알면 부모의 인덱스를 알 수 있음
장점: 구현이 쉬움
단점: 공집합인 노드에도 메모리를 부여함->메모리 낭비
링크표현: 포인터로 부모노드가 자식노드를 가리키게 하는 방식
노드->구조체로 구현, 링크->포인터로 구현(leftLink, rightLink)
typedef struct TreeNode {
int data;
struct TreeNode *left, *right; // 자기 참조 구조체. 이때까지는 TreeNode가 구조체 변수 이름.
}TreeNode //이때부터 구조체 타입으로 사용 가능-이진 트리 순회
전위 = preorder: V(root)->L(left)->R(right)
중위 = inorder: L->V->R
후위 = postorder: L->R->V (예시-디렉토리 총 용량 계산)
-재귀, 반복으로 구현(반복-스택 명시적 사용)
레벨 순회: 반복으로만(큐 명시적 사용)
재귀 구현
inorder(TreeNode *root) {
inorder(root->left);
print(root->data);
inorder(root->right);
}
preorder(TreeNode *root) {
print(root->data);
preorder(root->left);
preorder(root->right);
}
postorder(TreeNode *root) {
postorder(root->left);
postorder(root->right);
print(root->data);
}수식 트리: 비단말노드=연산자(operator), 단말노드=피연산자(operand)
#need_to_know
1. 이진 트리 순회 방식->재귀 구현은 쉬움. 그러나 빠르고 효율적이려면? 반복으로 구현해보기
2. 이진 트리 연산 코드 구현
3. 이진 탐색 트리
4. 스레드 이진 트리
+...
