22. 트리

트리

계층적인 구조를 갖는 자료구조로 노드와 간선으로 이루어져 있다.

트리는 하나의 루트 노드를 갖고, 각 노드는 0개 이상의 자식 노드를 갖는다.

 

트리의 특징

트리는 하나의 루트 노드를 갖는다.

루트 노드는 0개 이상의 자식 노드를 갖는다.

그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있으며, 이것이 반복적으로 정의된다.

 

여기까지 트리의 정의와 특징을 보고도 이해하기 어려울 수 있다. 갑자기 자식 노드, 루트 노드 등 우리가 처음 보는 용어들이 나타났으니 트리와 관련된 용어들부터 정리하도록 하자

---

트리와 관련된 용어

차수 (Degree) : 노드가 가지는 자식 노드의 수 (트리의 차수는 전체 노드 중 가장 큰 차수가 트리의 차수가 된다.)

루트노드 (Root) : 트리에서 최상위 노드를 의미한다. (루트 노드는 부모노드가 없다.)

리프노드 (Leaf) : 트리에서 자식 노드가 없는 노드를 의미한다.

내부 노드 (Internal Node) : 리프 노드를 제외한 모든 노드

레벨 (Level) : 루트 노드부터 해당 노드까지의 깊이 (루트 노드의 레벨은 0, 깊이라고도 한다.)

높이 (Height) : 트리에서 가장 깊은 노드의 레벨 (루트 노드의 높이는 0)

부모 노드 (Parent) : 어떤 노드의 바로 위에 있는 노드

자식 노드 (Child) : 어떤 노드의 바로 아래에 있는 노드

형제 (Sibling) : 같은 부모를 가지는 노드들

선조 노드 (Ancestor) : 어떤 노드에서 루트 노드까지 경로상에 있는 모든 노드

자손 노드 (Descendant) : 어떤 노드에서 리프 노드까지 경로상에 있는 모든 노드

서브트리 (SubTree) : 어떤 노드를 루트로 하는 트리

노드 수 : 트리에 포함된 전체 노드의 수

 

여기서 어떤 노드라는 것은 트리 내에 있는 모든 노드가 해당될 수 있다는 것이다.