구성

기본 용어

• node
  트리의 원소
  - Root node
  최상위 원소
  - 나머지 원소는 $\{n |n \in \N\}$에 대해 $T1,\;T2,\;...,\;Tn$의 분리집합으로 분리된다.
• 간선 edge
  • 상위 노드와 하위 노드를 연결한다.
• 차수 degree
  • degree of node
    현재 node에 연결된 sub node의 갯수
  • degree of tree
    degree of node의 최대값
• 높이 level
  • level of node
    현재 node에서 단말 까지의 edge의 수
  • level of tree
    level of node의 최대값
    즉 root에서 leaf까지의 edge의 수

노드 간 관계

• 형제 노드 sibling node
  • 한 노드의 child node들
• 조상 노드
  • root node를 포함해 간선으로 연결된 모든 node
• 자손 노드
  • 모든 하위 node
• sub tree
  • parent node와 연결된 edge를 끊어서 형성되는 트리
• 단말 노드 leaf node
  - 차수가 0인 노드
  
  

이진 트리 Binary tree

• child node가 2 이하인 트리
• leaf node를 제외한 모든 node가 정확히 2개의 child node만 갖는다면 포화 이진 트리 perfect binary tree
• leaf node를 제외한 모든 node가 정확히 1개의 child node만 갖는다면 편향 이진 트리 skewed binary tree
• 높이가 $l$인 이진 트리는 최소 $(h + 1)$개, 최대 $(2^{h+1}-1)$개의 노드를 갖는다.

씅질

• 노드 $i$의 부모 노드는 $\displaystyle\frac{i}{2}$
• 노드 $i$의 왼쪽 자식은 $2i$, 오른쪽 자식은 $2i + 1$
• level $n$의 시작 노드는 $2^n$

배열 표현

• 위 성질을 활용하려면 루트 노드 번호는 1이어야 함(0이면 자식의 번호가 0, 1이 되니까)
• 그래서 배열로 표현하려면 0은 비우고 1부터 활용해야 함
  
  

비선형 자료구조의 완전탐색

• tree, graph 등의 비선형 자료구조는 선후 연결관계를 알 수 없다.
  해서 BFS 또는 DFS가 쓰임