진짜 개발자
본문 바로가기

CS(Computer Science)/자료구조

자료구조 - 트리(Tree)란

728x90

트리란

- 노드들을 간선으로 연결한 계층형 자료구조

- 제일위의 하나의 노드를 루트노드로 하여 나머지 노드들이 간선으로 연결 됨

- 하나의 노드는 그자체로 트리이며 루트가 된다

용어

1. 노드의 차수 - 한노드가 가진 서브트리의 수

ex) A의 차수 : 3, B의 차수 : 2, C의 차수 : 0, D의 차수 : 3


2. 리프노드(단말,터미널) - 차수가 0인 노드

ex) 리프노드 : E, J, K, L, H, I


3. 자식 노드 - 노드에 연결된 서브트리의 루트노드들

ex) A의 자식노드 : B, C, D


4. 부모 노드 - 노드에 연결된 한단계 상위 레벨 노드

ex) I의 부모노드 : D


5. 형제 노드 - 부모가 같은 노드

ex) G, H, I 는 형제노드


6. 트리의 차수 - 트리노드들의 차수중 최대 차수

ex) 트리의 차수 : 3


7. 노드의 레벨 - 노드가 속한 트리의 깊이 

ex) A노드의 레벨 : 0


8. 트리의 깊이(높이) - 트리의 최대 레벨

ex) 트리의 깊이 : 3