Tree(1)

트리

논리적 계층, 계급적 특성을 가지는 개념.

트리의 구성

• 노드: 트리의 항목/트리에 저장되는 데이터 묶음
• 부모노드 - 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드로서 상위계층의 부모노드와 하위계층의 자식노드
• 루트노드 : 트리의 최상위 노드(부모가 없는 노드)
• 서브트리 : 부모 노드를 삭제하면 생기는 트리들
• 리프노드 : 트리의 맨 끝에 있으면서, 자신의 서브트리를 갖지 않는 노드

진입/진출 차수

• 루트 노드 - 진입차수 = 0
• 루트를 제외한 모든 노드의 진입 차수 = 1
• 리프노드 - 진출차수 = 0

트리의 레벨

• 노드의 레벨 : 루트로부터 그 노드까지 이어진 선(경로)의 길이

트리의 높이

• 트리의 높이 : 루트로부터 가장 멀리 있는 노드까지 이어진 선(경로)의 길이에 1을 더한 값

이진 트리

이진 트리의 정의

• 모든 노드의 차수가 2 이하인 트리
• 모든 노드가 2개 이하의 자식노드를 가지므로 방향성 개념 부여도 가능 (오른쪽 노드, 왼쪽 노드)

포화 이진트리

이진트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리(모두 2개의 노드를 가졌을 경우)

이진트리의 구현

배열을 이용한 이진트리 구현

• 트리가 완전 이진트리 혹은 포화 이진트리인 경우 낭비되는 공간이 없어 효율적
  • 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 메모리 낭비 증가

포인터를 이용한 이진트리의 구현

struct node {
  struct node *left;
  struct node *right;
  int info;
}
// *left *right는 link pointer

이진트리 연산

이진 트리 순회

이진 트리의 각 노드를 빠짐없이, 중복 없이 한 번씩 방문하는 것

• 이진트리의 전위 순회

  • 루트노드 - 왼쪽 자식노드 - 오른쪽 자식노드

  // 재귀함수 호출
  struct node *nodeptr;
  void preorder(struct node *tree_ptr) {
    if (tree_ptr) {
      printf("%d", tree_ptr->info);
      preorder(tree_ptr->left);
      preorder(tree_ptr->right);
    }
  }
  

• 이진트리의 후위 순회

  • 왼쪽 자식노드 - 오른쪽 자식노드 - 루트노드

• 이진트리의 순회 단위

  1. 루트 방문(P)
  2. 왼쪽 서브트리 순회(L)
  3. 오른쪽 서브트리 순회(R)

• 이진트리의 생성/삽입/삭제

  • 일반적인 이진 트리를 생성하는 것은 연결리스트 연산을 사용
  • 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하면 연결리스트의 삽입 연산을 사용

예시1) 이진트리의 노드 개수 세기 연산

int get_node_count(nodeptr *root){
  if (root == null) return 0;
  int result = 1;
  result = get_node_count((nodeptr*)root->left)
    +
    get_node_count((nodeptr*)root->right);
  return result;
}

예시2) 이진트리의 리프 개수 세기 연산

Int get_leaf_count(nodeptr (root)){
  int result = 0;
  if (root == null) {
    return 0;
  } else if (root->left == null && root->right == null) {
    return 1;
  }
  result = get_leaf_count((nodeptr*)root->left)
    +
    get_leaf_count((nodeptr*)root->right);
  return result;
}

• 일반트리를 이진트리로 변환
  • 일반트리를 구현할 때 이진트리를 고려하지 않으면 메모리 낭비가 발생, 이를 막기 위해 변환