자료구조

트리 (Tree)

dyeoma 2020. 7. 24. 16:40

기본 용어

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)
Skewed Tree

 

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