10-1 트리

1. 트리의 개념

① 트리

    - 사이클이 없는 연결 그래프

    - 조직도, 가계도, 컴퓨터에서 파일을 관리하는 디렉토리, 데이터베이스의 자료와 같이

       계층적인 관계를 표현하는데 용이

    - 비선형 자료구조이고 정렬이나 프로그래밍 언어 구문에서도 다양하게 사용함.

     - 선형-> 배열, 리스트

② 루트 트리

   - 루트(Root)는 트리의 제일 위쪽에 위치하는데 트리의 정점 중 하나가 루트로 지정된 트리

   - 트리를 구성하는 정점들 중 루트 이외의 나머지 정점들은 루트 밑에 계층적으로 놓임.

   - 루트 이외의 나머지 정점들은 루트로부터 연결되는 경로가 유일하게 존재함.

 

2. 트리의 주요 용어

① 주요 용어

   - 루트 : 트리의 시작 정점, 트리의 가장 높은 곳에 위치

   - 부모 : 어떤 정점의 한 단계 상위 정점

   - 자식 :  어떤 정점의 한 단계 하위 정점

   - 형제 : 같은 단계에 있으면서 부모가 같은 정점들

   - 잎 : 자식이 없는 정점

   - 내부 정점 :  잎이 아닌 정점

   - 조상 : 루트에서 어떤 정점에 이르는 경로에 포함된 모든 정점

   - 자손 :  어떤 정점에서 잎에 이르는 경로에 포함된 모든 정점

   - 차수 : 어떤 정점에 포하된 자식의 개수

   - 트리의 높이 : 트리가 가지는 가장 긴 경로

   - 숲 :  루트를 제거하여 얻은 부분 트리의 집합

 

3. 이진 트리

① 순서 트리  

  - 트리를 구성하는 정점의 순서에 따라 의미가 달라지는 트리

 

② k진 트리 : 모든 정점의 차수가 k이하인 트리

  - K가 2인 트리는 이진트리   

 

③ 이진트리 (Binary Tree)

  - 모든 정점의 차수가 2인 트리

  - 트리를 구성하는 부모가 갖는 자식의 수가 최대 2개인 트리

  - 순서 있는 데이터들의 삽입, 삭제, 정렬, 탐색 등을 효율적으로 할 수 있는 구조

  - 높이가 낮은 이진 트리가 좋다.

  - 완전 이진 트리 : 높이가 h일때, 레벨 1부터 h-1까지 모든 정점이 2개씩 채워져 있고, 

                               레벨 h는 왼쪽부터 정점이 채워져 있는 트리

  - 포화 이진 트리 :  완전 이진 트리의 특별한 경우이며 높이가 h일 때, 

                                레벨 1에서 h까지 모든 정점이 2개씩 채워져 있는 트리

  - 사향 이진 트리 : 왼쪽이나 오른쪽 부분 트리만 가지는 트리 (좋지 않음)

  - 이진트리를 표현하는 방법 : 배열과 연결리스트

     - 배열 : 다수의 행과 2개의 열로 이루어진 2차원 배열 이용

  - 각 행에는 정점의 값을 나타내고 2개의 열에는 왼쪽 자식인지 오른쪽 자식인지 데이터를 표기한다.

   위의 그림에서 열 1개 더 추가해야함