자료구조 : 이진 트리의 순회(Traversal)

ROK·2022년 10월 26일
0

열혈 자료구조

목록 보기
24/30

이진 트리의 순회

우선 순회가 필요한 이유는 앞서 코드에서

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->left != NULL)
    	free(main->left);
        
	main->left = sub;
}

free 함수를 호출해서 서브트리를 삭제했다.
이 때 삭제할 서브트리가 하나의 노드로 이루어져 있으면 문제되는 것이 없다. 하지만 여러개의 노드로 이루어져 있다면 메모리의 누수로 이루어진다.

그렇기 때문에 둘 이상의 노드로 이루어져있는 서브 트리를 완전히 삭제하려면 서브 트리를 구성하는 모든 노드를 대상으로 free 함수를 호출해야 한다.

모든 노드를 방문하는 것을 순회라고 한다.
트리의 순회는 연결 리스트의 순회와 달리 다른 방법이 필요하다.

순회의 세 가지 방법

트리를 대상으로 하는 대표적인 순회의 세 가지 방법

  • 전위 순회(Preorder Traversal) : 루트 노드를 먼저

  • 중위 순회(Inorder Traversal) : 루트 노드를 중간에

  • 후위 순회(Postorder Traversal) : 루트 노드를 마지막에

위 그림처럼 높이가 1인 이진 트리의 순회는 간단하다. 하지만 높이가 2이상인 이진 트리의 경우에는 구조가 재귀적이므로 재귀적으로 순회를 구현하면 된다.

순회의 재귀적 표현


위 그림은 루트 노드를 기준으로 왼쪽과 오른쪽에 서브 트리가 존재하는 가장 일반적인 모델이다.
이 트리를 대상으로 중위 순회를 할 경우 순회의 순서는

  • 왼쪽 서브 트리의 순회
  • 루트 노드의 방문
  • 오른쪽 서브 트리의 순회

순서로 진행이 된다.

이를 코드로 표현하면

void InorderTraverse(BTreeNode * bt)
{
	InorderTraverse(bt->left);
    printf("%d \n", bt->data);
    InorderTraverse(bt->right);
}

로 표현할 수 있다.

여기서 문제가 재귀의 탈출 조건이 정의되어 있지 않다.

재귀의 탈출 조건은 bt == NULL일 때이다.

따라서 순회의 재귀 함수는

void InorderTraverse(BTreeNode * bt)
{
	if (bt == NULL) return;
    
	InorderTraverse(bt->left);
    printf("%d \n", bt->data);
    InorderTraverse(bt->right);
}

순회 코드 구현

앞에서 트리를 만들면서 했던 헤더파일과 소스파일을 그대로 사용한다.

#include <stdio.h>
#include "BinaryTree.h"

void InorderTraverse(BTreeNode *bt)
{
   if (bt == NULL)
      return;

   InorderTraverse(bt->left);
   printf("%d \n", bt->data);
   InorderTraverse(bt->right);
}

int main()
{
   BTreeNode *bt1 = MakeBTreeNode();
   BTreeNode *bt2 = MakeBTreeNode();
   BTreeNode *bt3 = MakeBTreeNode();
   BTreeNode *bt4 = MakeBTreeNode();

   SetData(bt1, 1);
   SetData(bt2, 2);
   SetData(bt3, 3);
   SetData(bt4, 4);

   MakeLeftSubTree(bt1, bt2);
   MakeRightSubTree(bt1, bt3);
   MakeLeftSubTree(bt2, bt4);

   InorderTraverse(bt1);

   return 0;
}
profile
하루에 집중하자

0개의 댓글