[C로 만드는 자료구조]이진 트리(Binary Tree) - 순회

이진 트리(Binary Tree)

이번부터는 동적할당으로 만든 트리를 가정할 것입니다. C로는 동적할당을 통한 이진트리 구현이 불가능하기 때문에 임의로 연결한 동적 이진 트리를 통해서 확인해야합니다.

이진 트리(Binary Tree) - 순회

이진트리의 순회란 계층적 구조로 저장되어 있는 이진 트리의 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미합니다.

순회를 위해 수행할 수 있는 작업은 3가지로 정의 할 수 있습니다.

• 현재 노드를 방문하여 데이터를 읽는 작업 : D
• 현재 노드의 왼쪽 서브트리로 이동하는 작업 : L
• 현재 노드의 오른쪽 서브트리로 이동하는 작업 : R
  
  

이진 트리가 순환적으로 정의되어 구성있기 때문에 순회 작업또한 서브트리에 대해서 순환적으로 반복하여 완성해야합니다. 오른쪽 서브 트리보다 왼쪽 서브 트리에 대한 순회를 먼저 수행해야합니다.

이진 트리(Binary Tree) - 순회 종류

이진 트리의 순회에는 다음 세가지가 있습니다.

• 전위 순회(Preorder Traversal) : DLR
  
  
• 자손 노드보다 루트 노드를 먼저 방문!
  
  
• 중위 순회(Inorder Traversal) : LDR
  
  
• 왼쪽 -> 루트 -> 오른쪽 순으로 방문하여 출력
  
  
• 후위 순회(Postorder Traversal) : LRD
  
  
• 루트 노드보다 자손을 먼저 방문
  

이제 각 순회들의 ADT들을 알아 보겠습니다.

이진 트리(Binary Tree) - 순회 구현

1. 전위 순회

전위순회는 다음과 같은 순서로 트리를 읽어가게 됩니다.  다음의 경우의 ADT는 다음과 같이 구현이 됩니다.

• void Preorder()
  
  

  void Perorder(Tree *Target_Tree)
  {
      if (Target_Tree == NULL)
          return;
      printf("%d ", Target_Tree->key);
      Perorder(Target_Tree->Left);
      Perorder(Target_Tree->right);
  }

2. 중위 순회

중위순회는 다음과 같은 순서로 트리를 읽어가게 됩니다. 다음의 경우의 ADT는 다음과 같이 구현이 됩니다.

• void Inorder()
  
  

  void Inorder(Tree *Target_Tree)
  {
      if (Target_Tree == NULL)
          return;
      Inorder(Target_Tree->Left);
      printf("%d ", Target_Tree->key);
      Inorder(Target_Tree->right);
  }

   

3. 후위 순회

후위 순회는 다음과 같은 순서로 트리를 읽어가게 됩니다. 다음의 경우의 ADT는 다음과 같이 구현됩니다.

• void Postorder()
  
  

  void Postorder(Tree *Target_Tree)
  {
      if (Target_Tree == NULL)
          return;
      Postorder(Target_Tree->Left);
      Postorder(Target_Tree->right);
      printf("%d ", Target_Tree->key);
  }

  
  

다시한번 말하지만 트리를 C로 구현하는 것이 쉽지 않아서 일일이 노드를 연결한 동적노드에서 확인을 해야합니다. 다음 포스팅에서는 우선순위 큐(Priority Queue)와 힙(Heap)에 대해서 포스팅하겠습니다.