트리(Tree) 의 접근

“트리는 계층적 관계를 표현하는 자료구조이다.”

트리를 표현할 수 있는 것들

컴퓨터의 디렉터리 구조도 트리의 예가 되고, 집안의 족보나 기업 및 정부의 조직도도 트리의 예가 된다.

트리 관련 용어의 소개

• 노드: node
  • 트리 구성요소에 해당하는 간선 끝에 오는 요소
• 간선: edge
  • 노드와 노드를 연결하는 연결선
• 루트 노드: root node
  • 트리 구조에서 최상위에 존재하는 A와 같은 노드
• 단말 노드: terminal node, non terminal node
  • 아래로 또 다른 노드가 연겨로디어 있지 않은 노드
• 내부 노드: internal node, leaf node
  • 단말 노드를 제외한 모든 노드로 자식이 있는 노드

부모, 자식, 형제 등등 벌써아는 것들

이진트리와 서브트리

큰트리에 속하는 작은 트리를 가리켜 서브 트리 라 한다.

이진 트리는 다음 두 조건을 만족해야 한다.

• 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
• 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.
• 노드가 위치한 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

포화 이진 트리(Full Binary Tree) 와 완전 이진트리(Complete Binary Tree)

레벨 (level) 과 높이 (height)를 소개하겠다.

루트노드는 레벨 0 으로 시작해서 다음 자식노드는 1, 그다음 자식노드는 2 식으로 레벨이 높아진다.