트리

Tree = root + subtrees

• 루트 노드(root node) : 부모 노드가 없는 중심이 되는 노르[트리에서 단 1개만 존재]
  - ex) 1

 

• 서브 트리(sub tree) : 루트 노드를 제외한 나머지 노드
  - ex ) 2, 3, ..., 9 , 10
• 리프 노드(leaf node) : 자식 노드를 가지고 있지 않은 트리의 말단에 있는 노드
  - ex) 7, 8, 9, 10
  
  
• 부모 노드(parent node) : 어떤 노드와 간선으로 연결되어 있고 위에 있는 노드
  - ex) 2번 노드는 4,5 번 노드의 부모 노드
  
  
• 자식 노드(children node) : 어떤 노드와 간선으로 연결되어 있고 그 아래에 있는 노드
  - ex) 4,5번 노드의 부모는 2번 노드
  
  
• 형제 노드(sibling) : 같은 부모 노드를 가지는 노드
  - ex) 8,9번 노드는 5번 노드를 부모로 하는 형제 노드
  
  
• 노드의 크기(size) : 자신을 포함한 모든 자식 노드들의 개수
  
  
• 노드의 차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수
  - ex) 4번 노드의 차수는 1
  
  
• 노드의 깊이(depth) : 루트 노드에서 어떤 노드까지 도달하기 위해 거치는 정점의 개수
  ex) 6번 노드의 깊이는 2이다
  
• 트리의 레벨(level) : 트리의 각 층에 번호를 매긴 것이다. 루트의 레벨은 0이다.
  - ex) 6번 노드의 레벨은 2다
  
  
• 트리의 높이(height) : 가장 깊이가 깊은 노드의 깊이
  - ex) 트리의 높이는 3이다
  - 교재에 따라서 root node의 Level이 1부터 시작하는 경우도 있다