[자료구조] 트리, 이진트리

트리

• 비선형의 자료구조이다.
• 원소들 간의 1:n의 관계를 가지는 계층형 자료구조이다.
• 상위 원소에서 하위 원소로 내려가면서 확장되는 나무(트리)모양의 구조이다.

트리 정의

노드(node) : 트리의 원소

• 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.
  노드 중 최상위 노드를 루트(root)라 한다.
  나머지 노드들은 n(>=0)개의 분리 집합 T1...TN으로 분리될 수 있다.
• 간선(edge) : 노드와 노드를 연결하는 선으로 부모와 자식 노드를 연결
• 루트 노드(root node) : 트리의 시작 노드인 최상위 노드
• 형제 노드 : 같은 부모 노드의 자식 노드들
• 조상 노드 : 간선을 따라 루트노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리(sub tree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들

차수(degree)

• 노드의 차수 : 노드에 연결된 자식 노드의 수
• 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
• 단말 노드(리프 노드) : 차수가 0인 노드 즉, 자식 노드가 없는 노드

높이

• 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
• 트리의 높이 : 트리에 있는 높이 중에서 가장 큰 값, 최대 레벨

이진트리

• 차수가 2인 트리
• 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리(왼쪽, 오른쪽 자식 노드)
• 모든 노드들이 최대 2개의 서브트리를 갖는 형태의 트리

이진트리 특성

• 높이i(레벨 i)에서 노드의 최대 개수는 2^i개 이다.
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개이고 최대 개수는
  2^(h+1)-1개 이다.

이진트리 종류

포화 이진 트리(Full Binary Tree)

• 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
• 높이가 h일 때, 최대 노드 개수인 2^(h+1)-1개의 노드를 가지는 이진트리이다.

완전 이진 트리(Complete Binary Tree)

• 높이가 h이고 노드 수가 n 개일 때 포화 이지느리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진트리이다.

편향 이진 트리(Skewed Binary Tree)

• 높이가 h에 대한 최소 개수 노드를 가지면서 한쪽 방향의 자식 노드만을 가지는 이진트리이다.

이진트리 표현

배열을 이용한 이진 트리의 표현에 대한 단점

• 편한 이진 트리의 경우 사용하지 않는 배열 원소에 대한 메모리 공간 낭비
• 트리의 중간에 새로운 노드를 삽입하거나 기존 노드를 삭제할 경우 배열의 크기 변경 어려워 비효율적이다.

이진트리 순회 : 트리의 노드들을 체계적으로 방문하는 것

• 전위순회(preorder traversal) : VLR
  부모노드 방문 후, 자식 노드를 좌, 우 순서로 방문한다.

  preorder_travers(V)
    if(V is not null){
    visit(V);
    preorder_traverse(V.left);
    preorder_traverse(V.right);
    }
  END preorder_traverse

• 중위순회(inorder traversal) : LVR
  왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문한다.

  inorder_travers(V)
    if(V is not null){
    inorder_travers(V.left);
    visit(V);
    inorder_travers(V.right);
    }
  END inorder_travers

• 후위순회(postorder traversal) : LRV
  자식노드를 좌우 순서로 방문한 후, 부모노드로 방문한다.

  postorder_travers(V)
    if(V is not null){
    postorder_travers(V.left);
    postorder_travers(V.right);
    visit(V);
    }
  END postorder_travers