용어정리 헷갈리는 것만
- 노드(Node) : 트리의 기본 요소. 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것이다.
- 가지(Branch, Edge) : 노드와 노드를 연결하는 간선
- Root Node : 트리의 맨 위에 있는 노드이다. 위 예시에는 1 이다
- 차수, Degree : 각 노드에서 뻗어나온 가지의 수이다. 위 예시에는 1의 차수 = 2 / 2의 차수 = 2 / 4의 차수 = 1이다
- 트리의 차수 : 노드들의 차수 중에서 가장 많은 수를 의미한다. 위 예시에는 2이다.
- 단말 노드(Terminal Node = Leaf Node) : 자식이 하나도 없는 노드이다. 이 단말 노드의 차수는 0이다. 위 예시에는 5, 6, 7, 8이 단말노드이다.
- 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드이다. 위 예시에는 1, 2, 3, 4가 비단말 노드이다.
- 자식노드(Children Node) : 어떤 노드에 연결된 다음 레벨의 노드들을 의미한다. 만약 위 예시에서 2의 자식 노드는 4와 5가 된다.
- 부모노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드이다. 위 예시에서 8의 부모 노드는 4가 된다.
- 형제노드(Sibling) : 동일한 부모를 갖는 노드들을 의미한다. 위 예시에서 7의 형제노드는 7이 된다. (참고로 트리 구조상 위에 있을수록 촌수가 높다. 부모와 자식의 관계는 상대적이다. 즉, 2는 1의 자식노드이면서 4와 5의 부모노드이다.)
- Level : 루트 노드의 레벨을 1로 가정한 후 어떤 레벨이 L이면 자식 노드는 L+1이다.
- 깊이(Depth, Height) : 어떤 트리에서 노드가 가질 수 있는 최대의 레벨을 의미한다. 위 예시에서 깊이는 4이다.
- 그렇다면 트리의 순서는 어떻게 될까? Root -> 왼쪽 -> 오른쪽의 순서가 기본적이다.
코딩