[C++] 이진트리 코드 구현 방법 binary tree

▣ 트리 

 ●  트리의 특징

• 검색이 편리하다.
• 논리적 계층을 이루고 있다.
• 계급적 특성을 가진다.

 ●  트리의 구조

  ▷ 노드

• 트리의 항목으로 트리에 저장되는 데이터들을 말한다.

  ▷ 부모노드-자식노드

•   상하 계층구조로 이루어지고 직접 연결된 노드 관계를 가진다. 
•   상위계층 - 부모노드, 하위계층 - 자식노드

  ▷ 루트노드

•   트리에서 최상위 노드

  ▷ 서브트리

•   부모노드 삭제하면 생기는 트리들

  ▷ 리프노드

•   트리의 맨 아래에 위치한, 자신의 서브트리가 없는 노드

 ● 차수

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

 ● 레벨

• 노드의 레벨: 루트부터 해당 노드까지 이어지는 간선의 길이
• 루트노드의 레벨 = 0

 ● 높이

• 트리의 높이 = 루트로부터 가장 멀리 있는 노드까지 이어진 간선의 길이 + 1
• 루트노드만 있는 트리의 높이 = 1

 

▣ 이진 트리 

 ●  이진 트리란?

• 모든 노드의 차수가 2인 트리를 말한다.
• 실제 트리 중 가장 많이 사용하는 트리 구조다.
• 컴퓨터 내부에서 구현하기가 효율적이다.
• 자식노드가 항상 2개이기 때문에 오른쪽 노드, 왼쪽 노드로 방향을 가진다.

 ●  포화 이진 트리

• 이진 트리의 모든 레벨에서 허용 가능한 최대 개수 노드를 가지는 트리를 말한다.

 ●  완전 이진 트리

• 높이가 k인 이진트리가 0레벨부터 k-2 레벨까지 다 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽 방향으로 노드들이 차례로 채워진 트리를 말한다.

 ●  이진 트리 구현 방법

  ▷ 배열 이용해서 구현하기

•   트리가 완전이진트리나 포화이진트리면 낭비되는 공간이 없어서 효율적이다.

•   하지만, 트리가 깊어질수록 메모리(기억장소) 낭비가 2^n에 비례해서 심해질 수 있다.

• 위 예를 보면, 1+3+7개만큼 메모리 낭비가 된다. 그래서 보통은 이진트리 구현할 때 배열 사용 안한다.

  ▷ 포인터 이용해서 구현하기

• 이진트리는 노드의 자식이 2개이므로 링크를 2개 가지도록 연결리스트로 구현한다.
• 리프노드나 자식노드가 없는 경우에는 링크에 NULL이라고 표현한다.

• 노드 생성 코드

struct node{
    struct node *left;
    struct node *right;
    int info;
}

• 노드를 추가할 때는 연결리스트의 삽입 연산을 이용하면 된다.

 

 ●  이진 트리 순회

• 이진 트리의 모든 노드를 중복없이 한 번씩 방문하는 것을 말한다.

  ▷ 전위 순회

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

struct node *nodeptr;
void soonhwey(struct node *tree_ptr){
  if(tree_ptr){
    cout << tree_ptr->info;
    soonhwey(tree_ptr->left);
    soonhwey(tree_ptr->right);
  }
}
//재귀함수호출 recursive call 로 구현

  ▷ 후위 순회

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

struct node *nodeptr;
void soonhwey(struct node *tree_ptr){
  if(tree_ptr){
    soonhwey(tree_ptr->left);
    soonhwey(tree_ptr->right);
    cout << tree_ptr->info;
  }
}

  ▷ 중위 순회

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

struct node *nodeptr;
void soonhwey(struct node *tree_ptr){
  if(tree_ptr){
    soonhwey(tree_ptr->left);
    cout << tree_ptr->info;
    soonhwey(tree_ptr->right);
  }
}

 

 ●  이진 트리 생성/삽입/삭제

• 생성 - 첫 노드가 루트노드, 삽입연산으로 노드 추가
• 삽입 - 연결리스트의 삽입연산
• 삭제1 - 리프노드 삭제 시 리프노드를 가리키는 노드의 포인터 NULL로 바꿈.
• 삭제2 - 리프노드 외의 노드 삭제 시, 삭제하려는 노드의 자식노드에 대한 처리 추가로 필요.  

 

 ●  이진 트리 노드 개수 세는 연산 구현

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

 

 ●  이진 트리 리프 노드 개수 세는 연산 구현

int leaf_count(nodeptr *root){
  int result = 0;
  if(root==null){
    return 0;
  } else if(root->left == null && root->right == null){ //leaf node면
    return 1;
  }
  result = node_count((nodeptr*)root->left) +
           node_count((nodeptr*)root->right);
  return result;
}

 

이진트리를 많이 쓰는 이유는 기억공간을 많이 줄이기 위함이다. 메모리 효율을 위함!

자식노드를 2개보다 많이, 예를 들면 10개의 자식노드를 가지면 그만큼 포인터를 할당해서 메모리가 많이 낭비된다.