반응형

자료구조 트리(Tree)의 용어는 다음과 같다.



노드 : node

트리의 구성 요소에 해당하는 A,B,C,D,E,F와 같은 요소


간선 : edge

노드와 노드를 연결하는 연결 선


루트 노드 : root node

트리 구조에서 최상위에 존재하는 A와 같은 노드


단말 노드 : terminal node

아래로 또 다른 노드가 연결되어 있지 않은 E,F,C,D와 같은 노드


내부 노드 : internal node

단말 노드를 제외한 모든 노드 즉, A,B와 같은 노드







부모 노드(parent node)

노드 A는 노드 B,C,D의 부모 노드이다.


자식 노드(child node)

노드 B,C,D는 노드 A의 자식노드이다.


형제 노드(sibling node)

노드 B,C,D는 부모 노드가 같으므로, 서로 형제 노드라고 한다.



서브 트리(sub tree)


하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브 트리라 한다.


서브 트리 역시 서브 트리로 이루어 져 있고, 그 서브 트리 또한 다른 서브 트리로 이루어 져 있다. 즉, 트리는 재귀적(Recursive)이다.





원래 트리는 자식노드를 몇개를 가져도 상관 없지만, 보통의 우리가 쓰는 트리는 이진 트리(binary tree)를 자주 쓴다.



이진 트리(binary tree)란?


루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.


나뉘어지는 두 서브 트리 또한 이진 트리이다.


이진 트리 또한 재귀적(Recursive)이며, 재귀적으로 구현하는 사고가 중요하다.





반응형