트리

8장 트리

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

- 수식 표현이 미숙합니다. 추후 수정하겠습니다…ㅎㅎ

- 시험에 나올 것 같은 특징들을 위주로 적어봤습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

트리

• 정의 : 한 개 이상의 노드로 이루어진 계층적인 구조의 유한 집합.
• 루트(root) 노드 : 계층적인 구조에서 가장 높은 곳에 있는 노드
• 서브 트리 : 루트 노드의 자식을 루트로 삼는 트리
• 간선(edge) : 루트와 서브 트리의 연결선
• forest : 트리들의 집합, 트리의 루트가 제거된 것
• 루트를 제외한 나머지 모든 노드들은 선행자(부모)가 하나만 존재
• 순회 : 전위, 중위, 후위, 레벨 순회
• 전위, 중위, 후위 순회 = 스택 사용
• 레벨 순회 = 큐 사용
• 배열로 표현할 때 인덱스는 1부터 사용
• 부모 인덱스 = i/2, 왼쪽 자식 인덱스 = 2i, 오른쪽 자식 인덱스 = 2i + 1

이진 트리

• 정의 : 모든 노드가 2개의 서브 트리를 가지고 있는 트리
• 이진 트리는 일반 트리와 달리 노드를 하나도 갖지 않을 수 있다.(서브트리가 공집합 가능)
• 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하
• 서브 트리 간에 순서가 존재
• 서로 다른 모양의 이진 트리 개수 : (2n)! / (n!(n+1)!)
• 높이가 h인 이진 트리 : 최소 h개 노드, 최대 2^n-1개 노드
• 이진 트리 단말 노드수 - 차수가 2인 노드 수 = 1
• n개 노드의 최대 높이 = n, 최소 높이 = 로그 2의 n의 올림
• 이진 트리 총 링크 개수 : 2n
• 루트를 제외한 다른 노드들을 가리키는 링크 개수 : n-1
• NULL 링크 : n+1
• 일반적인 이진 트리 높이 = 로그 2의 n
• 평균적인 경우, 연산 시간 복잡도 = O(로그 2의 n)
• 최악의 경우, 연산 시간 복잡도 = O(n)

링크법으로 생성된 이진트리

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
  int data;
  struct TreeNode *left, *right;
} TreeNode;

//      15
//  4        20
//1        16   25

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, &n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, &n3, &n4};
TreeNode n6 = {15, &n2, &n5};
TreeNode *root = &n6;

//중위 순회
void inorder(TreeNode *root){
  if (root != NULL) {
    inorder(root->left); //왼쪽 서브트리
    printf("[%d] ", root->data); //루트
    inorder(root->right); //오른쪽 서브트리
  }
}

//전위 순회
void preorder(TreeNode *root){
  if(root != NULL) {
    printf("[%d] ", root->data); //루트
    preorder(root->left); //왼쪽 서브트리
    preorder(root->right); //오른쪽 서브트리
  }
}

//후위 순회
void postorder(TreeNode *root){
  if (root != NULL) {
    postorder(root->left); //왼쪽 서브트리
    postorder(root->right); //오른쪽 서브트리
    printf("[%d] ", root->data); //루트
  }
}

int main(void)
{
  printf("중위 순회 = ");
  inorder(root);
  printf("\n");

  printf("전위 순회 = ");
  preorder(root);
  printf("\n");

  printf("후위 순회 = ");
  postorder(root);
  printf("\n");

  return 0;
}