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

이진트리 (Binary Tree)란?

 이진트리는  모든 노드의 차수가 2 이하인 트리를 말한다. 다시 말해 하나의 노드가 가질 수 있는 자식 노드는 최대 2개라는 뜻이다. 

이진트리의 종류 

이진트리는 형태에 따라 3가지로 분류할 수 있다.

1) 포화 이진 트리(Full Binary Tree)

 포화 이진 트리는 모든 레벨의 노드가 가득 차 있는 이진트리를 말한다. 한 노드가 자식 노드를 가지게 된다면 무조건 자식 노드가 2개라는 뜻이다. 이러한 특징 덕분에 포화 이진트리에서 모든 노드의 개수는 다음과 같다. 
아래 그림은 포화 이진 트리의 예시이다.

출처: https://lovelyseoul.tistory.com/20

2) 완전 이진트리(Complete Binary Tree)

 완전 이진 트리는 높이가 h인 이진트리 일 때 h-1단계까지는 포화 이진트리와 동일하지만 h단계에서 노드가 포화 이진트리와 다르게 가득 차 있지 않다는 점에서 달라진다. h단계에서 노드가 존재해도 되지만 왼쪽부터 차례대로 채워져 있어야 한다. 빈 공간이 생기면 완전 이진트리가 아니다. 

출처: https://medium.com/@dltkddud4403/이진-트리가-완전-이진-트리인지-확인하는-알고리즘

 위 그림에서 A는 와전 이진 트리이고 B는 3단계에서 3번째 자리가 빈 공간이므로 완전 이진 트리가 아닌 그냥 이진 트리이다.

3) 편향 이진트리(Skewed Binary Tree)

 편향 트리는 말 그대로 한쪽으로만 자식 노드를 가지는 이진트리를 말한다.  
아래 그림은 편향 이진 트리의 예시이다.

출처: https://lovelyseoul.tistory.com/20

이진트리의 추상 자료형

 이진 트리 사용에 필요한 기본 연산을 정리한 이진트리의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다. 

이름		입력	출력	설명
이진 트리 생성	MakeBinTree()	원소 e	트리 T	원소 e를 루트 노드로 하는 이진트리T생성
루트 노드 반환	getRootNode()	트리 T	루트 노드 n	이진 트리의 루트 노드 n 반환
왼쪽 자식 노드 추가	inseertLeftChileNode()	노드 N	노드 n	부모 노드 N의 왼쪽 자식 노드 n 추가
오르쪽 자식 노드 추가	inseertRightChileNode()	노드 N	노드 n	부모 노드 N의 오른쪽 자식 노드 n 추가
왼쪽 자식 노드 반환	getLeftChildNode()	노드 N	왼쪽 자식 노드 n	노드 N의 왼쪽 노드 반환
오른쪽 자식 노드 반환	getRightChildNode()	노드 N	오른쪽 자식 노드 n	노드 N의 오른쪽 노드 반환
이진트리 루트 노드의 데이터 반환	getData()	트리 T	원소 e	트리 T의 루트 노드 데이터 반환
이진트리 삭제	deleteBinTree()	트리 T	N/A	이진 트리 메모리 해제

연결 리스트 이진트리의 구현

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

파일 이름	내용
binarytree.h	구조체 및 함수 선언
binarytree.cpp	함수 구현
BinaryTreeMain.cpp	main 함수 실행

1.binarytree.h

코드 구현은 다음과 같다.

#pragma once
#include<iostream>
#define TRUE 1
#define FALSE 0
struct BinTreeNode{
	int data;
	struct BinTreeNode* pLeftChild;
	struct BinTreeNode* pRightChild;
};
struct BinTree {
	BinTreeNode* pRootNode;
};
BinTree* MakeBinTree(BinTreeNode rootNode); //이진 트리 생성
BinTreeNode* getRootNode(BinTree* pBinTree);// 루트 노드 반환
BinTreeNode* inseertLeftChileNode(BinTreeNode* pParentNode,BinTreeNode element);// 왼쪽 자식 노드 추가
BinTreeNode* inseertRightChileNode(BinTreeNode* pParentNode, BinTreeNode element);// 오른쪽 자식 노드 추가
BinTreeNode* getLeftChildNode(BinTreeNode* pNode); // 왼쪽 자식 노드 반환
BinTreeNode* getRightChildNode(BinTreeNode* pNode); // 오른쪽 자식 노드 반환
// BinTreeNode* getData(); 
void deleteBinTree(BinTree* pBinNode); // 이진트리 삭제
void deleteBinTreeNode(BinTreeNode* pNode);// 노드 삭제

- BinTreeNode는 트리에 저장되는 각각의 자료들을 의미하며 실제값 data와 자식 노드를 가리키는 링크를 포함한다.
이때 이진 트리이므로 자식은 왼쪽 자식, 오른쪽 자식 최대 2개만 존재한다.
- BinTree는 실제 이진 트리를 의미한다. 내부 변수는 오직 루트 노드만 존재한다. 이 루트 노드의 링크를 이용해 모든 값에 접근할 것이다.

추가적으로 #define을 이용해 TURE은 1, FALSE는 0 값으로 정의해주었다. 

전체적인 형태는 다음과 같다.

2.binarytree.cpp

- MakeBinTree()

#include "binarytree.h"
using namespace std;
BinTree* MakeBinTree(BinTreeNode rootNode) {
	BinTree *pReturn = NULL;
	pReturn = (BinTree *)malloc(sizeof(BinTree));
	if (pReturn != NULL) {
		pReturn->pRootNode= (BinTreeNode *)malloc(sizeof(BinTreeNode));
		if (pReturn->pRootNode != NULL) {
			*pReturn->pRootNode = rootNode;
			pReturn->pRootNode->pLeftChild = NULL;
			pReturn->pRootNode->pRightChild = NULL;
		}
		else {
			cout << "메모리 할당 오류" << endl;
		}
	}
	else
		cout << "메모리 할당 오류" << endl;
	return pReturn;
} //이진 트리 생성

 입력 변수로 루트 노드가 될 값을 받고 루트노드로 설정한다. 설정 후 루트 노드의 자식 링크를 각각 NULL값으로 초기화해주고 이진트리를 반환한다.

- InsertChildNode()

자식노드를 추가하는 함수이다. 이진트리 이므로 왼쪽 자식 노드를 추가하는 함수( inseertLeftChileNode() ),
오른쪽 자식 노드( inseertRightChileNode() )를 추가하는 함수 2가지로 분류하였다. 함수에 대한 설명은 왼쪽 노드를 추가하는 함수를 이용하여 설명하겠다.

코드 구현은 다음과 같다.

BinTreeNode* inseertLeftChileNode(BinTreeNode* pParentNode, BinTreeNode element) {
	BinTreeNode* pReturn=NULL;
	if (pParentNode!= NULL) {
		if (pParentNode->pLeftChild == NULL) {
			pParentNode->pLeftChild = (BinTreeNode *)malloc(sizeof(BinTreeNode));
			*pParentNode->pLeftChild = element;
			pParentNode->pLeftChild->pLeftChild = NULL;
			pParentNode->pLeftChild->pRightChild = NULL;
			pReturn = pParentNode->pLeftChild;
		}
		else {
			cout << "이미 노드가 존재 합니다." << endl;
		}
	}
	return pReturn;
}// 왼쪽 자식 노드 추가

 먼저 부모 노드의 왼쪽 자식이 있는지 확인한다. 만약 있다면 오류 발생 문구를 출력하고 NULL값을 반환한다.
왼쪽 자식이 없다면 왼쪽 자식에 element값을 저장해주고 링크들을 재설정 해준다. 링크 재설정 후 반환 값을 설정해주고 반환한다.

*pParentNode->pLeftChild = element; // 부모 노드의 왼쪽 자식 링크를 element로 설정
pParentNode->pLeftChild->pLeftChild = NULL;  // 새로운 노드 자식링크 초기화
pParentNode->pLeftChild->pRightChild = NULL;  // 새로운 노드 자식링크 초기화
pReturn = pParentNode->pLeftChild; // 반환값 설정

추가로 inseertRightChileNode() 함수의 코드는 다음과 같다.

BinTreeNode* inseertRightChileNode(BinTreeNode* pParentNode, BinTreeNode element) {
	BinTreeNode* pReturn=NULL;
	if (pParentNode != NULL) {
		if (pParentNode->pRightChild == NULL) {
			pParentNode->pRightChild = (BinTreeNode *)malloc(sizeof(BinTreeNode));
			*pParentNode->pRightChild = element;
			pParentNode->pRightChild->pLeftChild = NULL;
			pParentNode->pRightChild->pRightChild = NULL;
			pReturn = pParentNode->pRightChild;
		}
		else {
			cout << "이미 노드가 존재 합니다." << endl;
		}
	}
    return pReturn;
}// 오른쪽 자식 노드 추가

- getNode()

이진 트리의 노드를 반환하는 함수는 3가지가 있다. 루트 노드 반환하는 함수( getRootNode() ), 왼쪽 자식 노드를 반환하는 함수 ( getLeftChildNode() ), 오른쪽 자식 노드를 반환하는 함수 ( getRightChildNode() )이다. 3가지 함수 노드 모두 그냥 해당 노드에 접근하여 원하는 값을 반환하기 때문에 별다른 코드가 없다.

BinTreeNode* getRootNode(BinTree* pBinTree) {
	BinTreeNode* pReturn = NULL;
	if (pBinTree != NULL) {
		pReturn = pBinTree->pRootNode;
	}
    return pReturn;
}// 루트 노드 반환

BinTreeNode* getLeftChildNode(BinTreeNode* pNode) {
	BinTreeNode* pReturn = NULL;
	if (pNode != NULL) {
		pReturn = pNode->pLeftChild;
	}
	return pReturn;
} // 왼쪽 자식 노드 반환

BinTreeNode* getRightChildNode(BinTreeNode* pNode) {
	BinTreeNode* pReturn = NULL;
	if (pNode != NULL) {
		pReturn = pNode->pRightChild;
	}
	return pReturn;
} // 오른쪽 자식 노드 반환

 

- deleteBinTree(), deleteBinTreeNode()

이진트리 노드와 이진 트리에 할당된 메모리를 해제하는 함수이다. deleteBinTree() 함수에서는 루트 노드에 할당된 메로리를 해제하기 위해 deleteBinTreeNode()를 호출하고 deleteBinTreeNode() 함수에서는 링크로 연결된 자식 노드들 까지 메모리 해제를 해줘야 하기 때문에 재귀 함수가 된다.

코드 구현은 다음과 같다.

void deleteBinTree(BinTree* pBinTree) {
	deleteBinTreeNode(pBinTree->pRootNode);
	free(pBinTree);
} // 이진트리 삭제
void deleteBinTreeNode(BinTreeNode* pNode) {
	if (pNode != NULL) {
		deleteBinTreeNode(pNode->pLeftChild);
		deleteBinTreeNode(pNode->pRightChild);
		free(pNode);
	}
}// 노드 삭제

 

 지금까지 구현한 함수들로는 트리안에 무슨 노드들이 저장되어 있는지 확인 하지 못한다. 트리 안에 저장된 노드들에 접근하기 위해서는 루트 노드를 이용해 트리안에 있는 모든 노드들을 순회해야 하는데 상당히 다양한 방법이 있기 때문에 다음 글에서 다루도록 하겠다.