C로 만드는 자료구조- 이진 트리의 순회

트리의 순회란?

 트리의 순회란 트리의 모든 모드를 한 번씩 방문 하는 것을 의미한다. 트리를 사용하면서 트리의 내용을 출력하거나 트리에서 원하는 노드를 찾고자 한다면  트리의 노드를 한 번씩 방문해야 한다. 근데 트리는 리스트,스택,큐와 같은 선형 자료구조가 아니라 계층 구조이기 때문에 순회 알고리즘을 잘 이해해야 하고 알고리즘에 방향성에 따라 다양한 순회 방법이 가능하다. 트리의 다양한 함수,알고리즘들은 기본으로 순회를 기반으로 하기 때문에 순회 알고리즘을 이해하고 사용용도에 따른 순회 알고리즘을 선택하는 것이 중요하다.

이진 트리의 순회

 이 글에서 다루는 것은 이진 트리의 순회를 다룰 것이다. 이진 트리는 최대 차수가 2이기 때문에 구성요소를 크게 3가지로 (L: 왼쪽 서브트리  R: 오른쪽 서브트리  V:현재 노드) 볼 수 있고 이 3가지를 방문하는 순서에 따라 순회 알고리즘이 달라진다.

이진 트리의 순회는 크게 3가지 순회 방법이 존재한다.

종류	방문 순서
전위 순회 (Preorder Travesal)	V-L-R
중위 순회 (Inorder Travesal)	L-V-R
후위 순회 (Postorder Travesal)	L-R-V

(L: 왼쪽 서브트리  R: 오른쪽 서브트리  V:현재 노드)

순회의 이름은 현재 노드를 언제 방문하느냐에 따라 정해진다. 전위 순회는 가장 먼저 현재 노드 방문 후 왼쪽 서브트리 오른쪽 서브트리 순으로 순회하고 중위 순회는 왼쪽 서브트리 방문 후 중간에 현재 노드를 방문하고 오른쪽 서브트리 순으로 순회한다. 후위 순회는 왼쪽 서브트리.오른쪽 서브트리를 방문하고 마지막에 현재 노드를 방문한다.

따라서 순회의 시작점은 항상 루트 노드이지만  순회 방식에 따라 방문하는 노드의 순서는 달라진다. 예를 들어 아래와 같은 이진 트리가 있을 때 순회 방식에 따른 방문 순서를 생각해보자

방문 순서는 아래 표와 같다.

종류	방문 순서
전위 순회 (Preorder Travesal)	A-B-D-E-C-F-G
중위 순회 (Inorder Travesal)	D-B-E-A-F-C-G
후위 순회 (Postorder Travesal)	D-E-B-F-G-C-A

 

이진트리의 순회 구현

 노드의 방문시 해당 노드의 데이터를 출력하는 방식으로 3가지 순회 방식에 따라 방문 노드를 차례대로 출력하는 함수를 각각 구현하고자 한다.

소스 파일 구성은 다음과 같다.

파일 이름	내용
binarytree.h	구조체 및 함수 선언
binarytree.cpp	함수 구현
binarytreetraversal.h	이진 트리 순회 함수 선언
binarytreetraversal.cpp	이진 트리 순회 함수 구현
BinaryTreeMain.cpp	main 함수 실행

binarytree.h , binarytree.cpp 는 이전 글의 코드를 그대로 사용한다.

C로 만드는 자료구조- 연결 리스트로 구현한 이진 트리

1. binarytreetraversal.h

코드는 다음과 같다.

#pragma once
#include"binarytree.h"

void PreorderBinTree(BinTree *pBinTree);
void PreorderBinTreeNode(BinTreeNode *pRootNode);

void InorderBinTree(BinTree *pBinTree);
void InorderBinTreeNode(BinTreeNode *pRootNode);

void PostorderBinTree(BinTree *pBinTree);
void PostorderBinTreeNode(BinTreeNode *pRootNode);

순서대로 전위 순회 함수,중위 순회 함수, 후위 순회 함수를  선언해 주었다. PreorderBinTree()가 순회 함수이고 PreorderBinTreeNode() 가 실질적으로 트리내부에서 순회를 수행하는 함수이다.

2. binarytreetraversal.cpp

 순회 함수의 구현은 재귀를 이용하면 생각보다 간단하다. 앞서 말했듯이 방문순서만 잘 생각해주면 된다. 추가적으로 항상 현재 노드를 방문할 때만 데이터 내용을 출력한다.

 

1. 전위 순회(Preorder Travesal)

#include"binarytree.h"
#include "binarytreetraversal.h"

void PreorderBinTree(BinTree *pBinTree) {
	if (pBinTree != NULL) {
		PreorderBinTreeNode(pBinTree->pRootNode);
	}
}
void PreorderBinTreeNode(BinTreeNode *pRootNode) {
	if (pRootNode != NULL) {
		printf("%c", pRootNode->data);
		PreorderBinTreeNode(pRootNode->pLeftChild);
		PreorderBinTreeNode(pRootNode->pRightChild);
	}
}

2. 중위 순회(InorderTravesal)

void InorderBinTree(BinTree *pBinTree) {
	if (pBinTree != NULL) {
		InorderBinTreeNode(pBinTree->pRootNode);
	}
}
void InorderBinTreeNode(BinTreeNode *pRootNode) {
	if (pRootNode != NULL) {
		InorderBinTreeNode(pRootNode->pLeftChild);
		printf("%c", pRootNode->data);
		InorderBinTreeNode(pRootNode->pRightChild);
	}
}

3. 후위 순회(Postorder Travesal)

void PostorderBinTree(BinTree *pBinTree) {
	if (pBinTree != NULL) {
		PostorderBinTreeNode(pBinTree->pRootNode);
	}
}
void PostorderBinTreeNode(BinTreeNode *pRootNode) {
	if (pRootNode != NULL) {
		PostorderBinTreeNode(pRootNode->pLeftChild);
		PostorderBinTreeNode(pRootNode->pRightChild);
		printf("%c", pRootNode->data);
	}
}

3. BinaryTreeMain.cpp

#include"bintree.h"
#include"binarytreetraversal.h"

int main()
{
//트리 생성
	BinTree *pBinTree = NULL;
	BinTreeNode *pNode1 = NULL, *pNode2 = NULL, *pNode3 = NULL, *pNode4 = NULL,
		*pNode5 = NULL, *pNode6 = NULL , *pNode7 = NULL;
	BinTreeNode node = { 0, };

	node.data = 'A';
	pBinTree = MakeBinTree(node);

	if (pBinTree != NULL) {
		
		pNode1 = getRootNode(pBinTree);

		node.data = 'B';
		pNode2 = inseertLeftChileNode(pNode1, node);

		node.data = 'C';
		pNode3 = inseertRightChileNode(pNode1, node);

		node.data = 'D';
		pNode4 = inseertLeftChileNode(pNode2, node);

		node.data = 'E';
		pNode5 = inseertRightChileNode(pNode2, node);

		node.data = 'F';
		pNode6 = inseertLeftChileNode(pNode3, node);

		node.data = 'G';
		pNode7 = inseertRightChileNode(pNode3, node);

	}
// 순회를 이용해 트리 출력
	if (pBinTree != NULL) {
		printf("Preorder Traversal\n");
		PreorderBinTree(pBinTree);

		printf("\nInorder Traversal\n");
		InorderBinTree(pBinTree);

		printf("\nPostorder Traversal\n");
		PostorderBinTree(pBinTree);
		printf("\n");
		deleteBinTree(pBinTree);
	}

    return 0;
}

출력 결과는 다음과 같다