이진트리 - 종류, 구현, 전위-중위-후위순회

이진트리

• 최대 2개의 자식을 가질 수 있는 트리

• 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아짐

• 데이터 저장, 탐색 등의 다양한 목적에서 사용 가능
  ​
  ​

트리 용어

• 길이: 출발 노드에서 목적지 노드까지 거쳐야하는 가짓수

• 깊이: 루트 노드에서 특정 노드까지의 길이

• 높이: 루트 노드에서 가장 깊은 노드까지의 길이
  ​
  ​

트리 종류

1. 포화 이진트리(Full Binary Tree)
   리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리
   ​
   ​
2. 완전 이진트리(Complete Binary Tree)
   모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드
   ​
   ​
3. 높이 균형트리(Height Balanced Tree)
   왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이나지 않는 트리
   ​
   ​

이진트리의 구현

typedef struct{
 int data;
 struct Node *leftChild;
 struct Node *rightChild;
} Node;
​
Node *initNode(int Data, Node *leftChild, Node *rightChild)
{
 Node *node;
 node = (Node*)malloc(sizeof(Node));
 node->data = data;
 node->leftChild = leftChild;
 node->rightChild = rightChild;
 return node;
}

​
​
​

이진트리의 순회

1. 전위순회
   (1) 자기 자신을 출력
   (2) 왼쪽 자식 방문
   (3) 오른쪽 자식 방문
   ​

   void preorder(Node *root)
   {
       if (root)
       {
           printf("%d ", root->data);
           preorder(root->leftChild);
           preorder(root->rightChild);
       }
   }

   ​

2. 중위순회 (왼쪽부터 출력하게 됨)
   (1) 왼쪽 자식 방문
   (2) 자기 자신 출력
   (3) 오른쪽 자식 방문
   ​

   void inorder(Node *root)
   {
     if (root)
     {
       inorder(root->leftChild);
       printf("%d ", root->data);
       inorder(root->rightChild);
     }
   }

   ​

3. 후위순회 (루트가 가장 마지막에 출력)
   (1) 왼쪽 자식 방문
   (2) 오른쪽 자식 방문
   (3) 자기 자신 출력
   ​

   void postorder(Node *root)
   {
     if (root)
     {
       postorder(root->leftChild);
       postorder(root->rightChild);
       printf("%d ", root->data);
     }
   }