트리 구조의 용어 정리
트리 : 1:n의 비선형 자료구조이며 계층 관계로 만들어진 계층형 자료구조라고 합니다.
노드 : 자료구조의 단위, 트리 자료구조에서는 1:n의 관계를 가집니다
간선 : 노드와 노드 사이의 관계를 나타내주는 실선
루트 노드 : 최상위 노드
부모 노드 : 간선으로 이어진 두 노드 중 루트노드에 더 가까운(레벨이 더 낮은) 노드
자식 노드 : 간선으로 이어진 두 노드 중 루트노드에 더 먼(레벨이 더 높은) 노드
형제 노드 : 같은 부모 노드를 가진 자식노드
레벨, 깊이 : 루트 노드를 0으로 하고 루트 노드와 해당 노드 사이의 간선의 수를 값으로 가집니다.
높이 : 루트에서 해당 노드에 이르는 경로에 있는 간선의 수, 트리의 높이는 최대 레벨과 같습니다.
서브트리 : 자식노드가 독립할 경우 만들 수 있는 트리
차수 : 서브트리의 수(자식 노드의 수)
단말 노드, 리프 노드 : 차수가 0인 노드
내부 노드 : 차수가 1 이상인 노드
포레스트 : 여러 개의 트리의 집합
이진 트리
이진 트리란?
트리의 모든 노드의 차수를 2 이하로 제한하요 전체 트리의 차수가 2 이하가 되도록 만든 트리입니다.
자식 노드는 왼쪽 노드이거나 오른쪽 노드일 수 있고 그 위치에 따라 구분짓습니다.
높이가 h라면 노드의 개수 n의 범위는 다음과 같습니다
이진트리는 레벨과 노드 수의 관계에 따라 포화 이진 트리, 완전 이진 트리, 편향 이진 트리로 특정지을 수 있습니다.
완전 이진 트리 : 루트 노드를 1로 하고 왼쪽에서 오른쪽으로 오름차순으로 레벨을 높여가며 번호를 붙일 때 특정 번호까지의 노드가 존재하고 그 이후의 노드가 공백일 때의 경우입니다.
포화 이진 트리 : 모든 레벨의 노드가 꽉 차 높이를 늘이지 않으면 노드를 추가할 수 없는 경우입니다. 최대 노드 수를 가지고 있습니다.
편향 이진 트리 : 모든 부모 노드의 자식노드가 같은 방향일 때 입니다. 최소 노드 수를 가지고 있습니다.
이진 트리의 구현
1.
순차 자료구조
각 레벨의 최대 노드 개수는 해당 레벨의 2배이기때문에 배열로 구현할 수 있습니다.
이 때 계산의 용이성을 위해 0번 인덱스를 비워 루트 노드의 인덱스를 1로 정한다면 부모 노드에 접근할 땐 i / 2,왼쪽 자식노드는 2 * i, 오른쪽 자식 노드는 2 * i + 1로 접근 가능합니다.
2.
연결 자료구조
norme에 맞게 만든다면 이런 구조가 될 것 같습니다.
typedef struct s_btree
{
struct s_btree *left;
struct s_btree *right;
void *content;
} t_btree;
C
복사
이진 트리의 순회
한 노드에서 할 수 있는 작업은 3가지입니다
•
작업 D : item에 접근한다
•
작업 L : left에 접근한다
•
작업 R : right에 접근한다
•
자식 노드에 접근할 때 왼쪽 노드에 우선적으로 접근합니다.
•
해당 노드의 Data에 접근하는 순서를 기준으로 순회의 종류를 나눕니다.
전위 순회
•
D → L → R
중위 순회
•
L → D → R
후위 순회
•
L → R → R
모든 data가 다르고 전위 순회의 결과와 중위 순회의 결과를 알고있다면 해당 이진 트리의 구조를 알아낼 수 있습니다
1.
1사분면이 나오도록 수직선을 그립니다
2.
중위 순회의 결과를 가로로 적습니다
3.
전위 순회의 결과를 위에서 아래로 세로로 적습니다
4.
두 순회의 data가 일치하는 경우를 표기합니다
5.
가장 위의 노드가 루트 노드입니다
6.
조상 노드를 넘지 않는 영역에서 부모 노드에 가장 가까운 노드가 자식노드입니다.
출처 : C로 배우는 쉬운 자료구조 4판 (이지영/한빛아카데미)
