트리 (Tree)
기본 용어
Tree 정의 : node로 이루어진 유한집합으로 root node와 나머지 노드 (T_1, T_2, ..., T_n)으로 분리.
이때 T_i는 각각 하나의 tree (sub tree 혹은 부분 tree)라 함

node의 차수(degree) | 해당 node의 sub tree 수 |
tree의 차수 | tree에 포함된 node들 중 최대 차수 |
리프(leaf) 또는 단말노드(terminal) | 차수가 0인 node ex) K, L, F, G, M, I, J |
비단말노드(non-terminal) | 차수가 0이 아닌 node ex) A, B, C, D, E, H |
레벨(level) | root level이 1일 때 부모-자식은 1 level씩 증가 |
tree 깊이(depth) 또는 높이(height) | tree에 속한 node의 최대 level |
부모(parent), 자식(child), 조상(ancestor), 자손(descentdant)
트리의 표현 - 리스트
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
이진 트리 (Binary Tree)
정의 : 모든 노드의 차수가 2 이하인 tree
편향 트리 (Skewed Tree) | 포화이진트리 (Full Binary Tree) | 완전 이진트리 (Complete Binary Tree) |
깊이가 k이고 node 수가 (2^k)-1인 이진 트리 | 깊이가 k이고 node 수가 n인 이진 트리의 각 node들이 깊이 k인 포화이진트리에서 1부터 n까지의 번호를 붙인 node들과 1대1로 일치하는 이진트리. 높이는 log_2(n+1) | |
![]() |
![]() |
![]() |
Binary Tree의 성질
1. 이진 트리 level i에서의 최대 노드 수 : 2^(i-1) (i≥1)
2. 깊이가 k인 이진트리의 최대 노드 수 : (2^k)-1 (k≥1)
3. 공백이 아닌 모든 이진트리 T에 대해,
n_0 = 단말 노드 수, n_2=차수가 2인 노드 수 일 때,
n_0 = n_2 + 1
1차원 배열 표현
n개의 node를 가진 완전이진트리에 대해
parent(i) = i/2 (i≠1)
leftChild(i) = 2i (2i≤n)
rightChild(i) = 2i+1 (2i+1≤n)
![]() |
![]() |
Tree - 링크 표현
![]()
|
![]() |
![]() |
![]() |
Node - 링크 표현


이진 트리 순회 : tree에 있는 각 node를 한 번씩 방문하는 방법
전위 (preorder) | root - left subtree - right subtree |
중위 (inorder) | left subtree - root - right subtree |
후위 (postorder) | left subtree - right subtree - root |
ex)

preorder : a b d e c f g
inorder : d b e a f c g
postorder : d e b f g c a
산술식 이진트리 표현

중위순회 : A/B*C*D+E
전위순회 : +**/ABCDE
후위순회 : AB/C*D*E+
반복적 중위 순회
![]() |
stack | |||||||||||||||||
H D B A |
D B A |
B A |
I B A |
B A |
A |
E A |
A |
- |
C |
F C |
C |
- |
G |
- |
출력 : H D I B E A F C G