10-1 트리와 이진트리

1. 트리의 개념

① 트리

  -  원소들 간에 1:n 관계를 가지는 비선형 자료구조

  -  원소들 간에 계층관계를 가지는 계층형 자료구

 

② 트리의 구조와 구성 요소

  - 서브 트리(Subtree) :  부모 노드와 연결된 간선을 끊었을 때 생성되는 트리로

                                      각 노드는 자식노드의 개수 만큼 서브 트리를 가짐.

  - 노드의 차수 : 노드에 연결된 자식 노드의 수

  - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값

  - 높이 -> 노드의 높이 : 루트에서 노드에 이르는 간선의 수

             -> 트리의 높이: 트리에 있는 노드 높이 중에서 가장 큰 값이며 최대 레 

③ 포리스트(Forest) : 서브트리의 집합

  - 트리 A에서 노드 A를 제거하면 A의 자식 노드 B,C,D에 대한 서브트리가 생기고, 이들의 집합이 포리스트

 

2. 이진트리의 이해와 종류

① 이진 트리 

  - 트리의 모든 노드의 차수를 2이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의

 

② 일반 트리를 이진 트리로 변환

③ 이진 트리의 추상 자료형에 따라 만들어진 이진 트리 특징

  - 노드가 n개인 이진 트리는 항상 간선이 n-1개 (루트노드는 엣지가 없기에)

  - 높이가 h인 이진 트리가 가질 수 있는 노드의 개수는 최소 (h+1), 최대 (2^h+1 -1)

④ 이진 트리의 종류

  - 일반적인 이진 트리 외에 레벨과 노드 수의 관계에 따라 포화 이진 트리, 완전 이진트리, 편향 이진 트리가 있음.

  - 포화 이진 트리 : 모든 레벨에 노드가 포화상태로 차 있는 이진 트리

                              -> 높이가 h일 때, 최대의 노드 개수인 2^h+1-1의 노드를 가진 이진 트리

  - 완전 이진 트리 : 높이가 h이고 노드 수가 n(n<2^h+1 >  최대 노드 수보다 작)개일 때,

                               노드 위치가 포화 이진 트리에서

                               노드 1번부터 n번 까지의 위치와 완전히 일치하는 이진 트리

  - 편향 이진 트리 : 높이가  h일 때 h+1개의 노드를 가지면서

                                   모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브 트리를 가지고 있는 트리.

3. 순차 & 연결 자료구조를 이용한 이진 트리 구

① 순차 자료구조를 이용한 이진 트리의 구현

  - 인덱스 0번 : 실제로 사용하지 않고 비워둠.

② 연결 자료 구조를 이용한 이진 트리의 구조

  - 포인터를 사용하여 이진트리 구현 : 데이터를 저장하는 데이터 필드, 왼쪽 자식 노드를 연결하는 왼쪽 링크 필드, 오른쪽 자식 노드를 연결하는 오른쪽 링크 필드로 구성 

완전 이진 트리