반응형
자료구조 트리(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)이며, 재귀적으로 구현하는 사고가 중요하다.
반응형
'Applied > 자료구조' 카테고리의 다른 글
연결 리스트(Linked List) 개념 (1) (0) | 2016.05.03 |
---|---|
트리(Tree) 용어 (2) (0) | 2016.05.01 |
배열 기반 Bag 자료구조 소스 코드 (0) | 2016.04.21 |
배열 기반 Bag 자료구조 개념 (0) | 2016.04.21 |
이중 연결 리스트 기반 데크(Dequeue) 소스 코드 (0) | 2016.04.13 |