트리 level 1 (트리 기본, just Tree...)

1) 트리(Tree)

  - 정점(node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조

 

 

2) 트리 관련 용어

  - 정점(node) : 데이터를 담고 있는 요소

  - 간선(edge) : 노드와 노드를 잇는 연결선

  - 뿌리(root) : 최상위 노드로 자식 노드만 가질 수 있는 노드

  - 잎(leaf) : 최하위 노드로 자식 노드를 가질 수 없는 노드

  - 부모(parent) : 연결된 두 노드 중 뿌리(root)에 가까운 노드

  - 자식(child) : 연결된 두 노드 중 잎(leaf)에 가까운 노드

  - 형제(sibling) : 같은 부모를 가진 노드

  - 조상(ancestor) : 뿌리 방향으로 가며 만나는 노드들

  - 후송(descendant) : 잎 방향으로 가며 만나는 노드들

  - 수준(level)

• Root를 기준으로 Leaf 방향으로 넘어가며 거쳐가는 edge의 개수
• 종종 root의 수준을 1로 정의하기도 하지만, root노드로부터 해당 node까지의 간선의 수로 노드의 수준을 정의하면 root노드를 level 0으로 정의하는 것이 났다

  - 높이(Heigt) 또는 깊이(Depth) : 루트로부터 하위 계층 노드까지 거쳐가는 간선의 수 → height(depth) = 최대 level + 1

  - 부분트리(Subtree) : 트리 내에서 특정 노드를 루트 노드로 삼아 형성된 트리 

  - 차수(degree) : 특정 노드의 부분트리 갯수 → 차수가 0이면 leaf노드에 해당

  ※ 루트 노드를 제외하면 모든 노드는 parent로 가는 간선은 오직 하나이다.