C로 만드는 자료구조- 이진 트리 연산

이전글에서 이진 트리의 순환을 다루었다.

dsbook.tistory.com/245(이전 글)

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

이번 글에서는 이진 트리의 함수들을 다루고자 한다. 

1) 복사 

2) 동일성 검사

3) 노드 개수 구하기

4) 단말 노드 구하기 

5) 이진 트리의 높이 구하기

 위 함수들은 이진 트리의  구조와 순환 알고리즘들을 정확하게 이해하고 있다면 별다른 어려움 없이 구현이 가능하다. 이때 중요한점은 각 전위 순환, 중위 순환 ,후위 순환 알고리즘 중에서 함수에 적합한 순환 알고리즘을 선택하는 것이다.

코드 구현

 이전 글에 사용된 코드를 그대로 사용하되 위 5개의 함수를 구현할 binaryop.h ,binaryop.cpp 파일을 추가해준다.

#pragma once
#include"binarytree.h"

BinTree* copyBinTree(BinTree* pSource); // 복사
BinTreeNode* copyBinTreeNode(BinTreeNode* pSourceNode);

int equalBinTree(BinTree* pFirst, BinTree* pSecond); // 동일성 검사
int equalBinTreeNode(BinTreeNode* pFirst, BinTreeNode* pSecond);

int getNodeCount(BinTree *pSource); // 노드 개수 구하기
int getNodeCountNode(BinTreeNode *pSource);

int getLeafNodeCount(BinTree *pSource); // 단말 노드 구하기
int getLeafNodeCountNode(BinTreeNode *pSource);

int getHeight(BinTree *pSource); // 이진 트리의 높이 구하기 
int getHeightNode(BinTreeNode *pSource);

 위와 같이 binarypo.h에 함수들을 선언 해준다. 

1) 복사 

 기존에 만들어놓은 이진 트리와 똑같은 이진트리를 만드는 것을 의미한다. 이 함수를 구현하기 위해서는 전위 순회 방식을 이용해야한다. 즉 현재 노드를 먼저 복사하고 왼족 서브트리,오른쪽 서브트리 순으로 복사를 한다는 것이다.  트리를 만들때 부모 노드에 자식노드를 추가하는 형식이기 때문에 후위,중위 순회 방식을 사용하지 못한다.

코드는 다음과 같다.

BinTree* copyBinTree(BinTree* pSource) { // 복사
	BinTree* pReturn = NULL;
	if (pSource != NULL) {
		pReturn = (BinTree *)malloc(sizeof(BinTree));
		if (pReturn != NULL) {
			pReturn->pRootNode = copyBinTreeNode(pSource->pRootNode);
		}
	}
	return pReturn;
}
BinTreeNode* copyBinTreeNode(BinTreeNode* pSourceNode) {
	BinTreeNode* pReturn = NULL;
	if (pSourceNode != NULL) {
		pReturn = (BinTreeNode *)malloc(sizeof(BinTreeNode));
		if (pReturn != NULL) {
			*pReturn = *pSourceNode;
			pReturn->pLeftChild = copyBinTreeNode(getLeftChildNode(pSourceNode));
			pReturn->pRightChild = copyBinTreeNode(getRightChildNode(pSourceNode));
		}
	}
	return pReturn;
}

아래 코드를 통해 전위 순회 방식을 이용했음을 알 수 있다.

if (pReturn != NULL)
{ *pReturn = *pSourceNode;  // 현재 노드
   pReturn->pLeftChild = copyBinTreeNode(getLeftChildNode(pSourceNode)); // 왼쪽 서브트리 
   pReturn->pRightChild = copyBinTreeNode(getRightChildNode(pSourceNode));  // 오른쪽 서브트리
}

2) 동일성 검사 

 2개의 이진 트리가 동일한지 검사하는 함수이다. 여기서 동일하다는 것은 구조와 노드이 저장된 자료가 다 일치할 때를 말한다. 만약 동일하다면 TRUE(1)을 반환하고 동일하지 않는다면 FALSE(0) 을 반환한다. 이 함수를 구현하기 위해서 전위 순회 방식을 이용하였다. 먼저 현재 노드에 저장된 자료를 비교한 후 왼쪽 서브트리, 오른쪽 서브트리 순으로 비교한다.

코드는 다음과 같다.

int equalBinTree(BinTree* pFirst, BinTree* pSecond) { // 동일성 검사
	int ret = FALSE;
	if (pFirst == NULL && pSecond == NULL) {
		ret = TRUE;
	}
	else if (pFirst != NULL && pSecond != NULL && equalBinTreeNode(pFirst->pRootNode, pSecond->pRootNode) == TRUE) {
		ret = TRUE;
	}
	return ret;
}
int equalBinTreeNode(BinTreeNode* pFirst, BinTreeNode* pSecond) {
	int ret = FALSE;
	if (pFirst == NULL && pSecond == NULL) {
		ret = TRUE;
	}
	else if (pFirst != NULL && pSecond != NULL 
		&& pFirst->data==pSecond->data
		&& equalBinTreeNode(pFirst->pLeftChild, pSecond->pLeftChild) == TRUE
		&& equalBinTreeNode(pFirst->pRightChild,pSecond->pRightChild)==TRUE) {
		ret = TRUE;
	}
	return ret;
}

아래 코드를 통해 전위 순회 방식을 이용했음을 알 수 있다.

else if (pFirst != NULL && pSecond != NULL &&
          pFirst->data==pSecond->data &&  // 현재 노드
          equalBinTreeNode(pFirst->pLeftChild, pSecond->pLeftChild) == TRUE && //왼쪽 서브트리
          equalBinTreeNode(pFirst->pRightChild,pSecond->pRightChild)==TRUE) //오른쪽 서브트리
         { ret = TRUE; }

3) 노드 개수 구하기

 이진 트리의 모든 노드 개수를 구하는 함수이다. 구현하기 위해서 후위 순회 방식 이용해야 한다. 왼쪽 서브트리이 노드 개수, 오른쪽 서드 트리의 노드 개수를 구하고 현재 노드인 1을 더해주면 노드 개수의 총 개수를 구할 수 있다. 이때 전위, 중위 순환 방식을 사용하면 양쪽 서브 트리의 개수를 구하기 전에 현재 노드에 방문하기 때문에 부적절하다.

코드는 다음과 같다.

int getNodeCount(BinTree *pSource) { // 노드 개수 구하기
	int ret = 0;
	if (pSource != NULL) {
		ret = getNodeCountNode(pSource->pRootNode);
	}
	return ret;
}
int getNodeCountNode(BinTreeNode *pSource) {
	int ret = 0;
	if (pSource != NULL) {
		ret = getNodeCountNode(pSource->pLeftChild) +
			getNodeCountNode(pSource->pRightChild) + 1;
	}
	return ret;
}

아래 코드를 통해 후위 순회 방식을 이용했음을 알 수 있다.

if (pSource != NULL)
 { ret = getNodeCountNode(pSource->pLeftChild) //왼쪽 서브트리
          + getNodeCountNode(pSource->pRightChild)  // 오른쪽 서브트리
          + 1; } // 현재노드

4) 단말 노드 개수 구하기

 이진 트리의 단말 노드의 개수를 구하는 함수이다. 단말 노드는 자식노드가 없는 노드를 의미한다. 단말 노드의 개수를 구하는 방식은 위에서 한 노드 개수 구하기와 비슷하지만 오직 자식 노드가 없는 단말 노드에 방문 했을때만 1을 더해주는 것만 주의하면 된다.

코드는 다음과 같다.

int getLeafNodeCount(BinTree *pSource) { // 단말 노드 구하기
	int ret = 0;
	if (pSource != NULL) {
		ret = getLeafNodeCountNode(pSource->pRootNode);
	}
	return ret;
}
int getLeafNodeCountNode(BinTreeNode *pSource) {
	int ret = 0;
	if (pSource != NULL) {
		if (pSource->pLeftChild == NULL && pSource->pRightChild == NULL) {
			ret = 1;
		}
		else {
			ret = getLeafNodeCountNode(pSource->pLeftChild)
				+ getLeafNodeCountNode(pSource->pRightChild);
		}
	}
	return ret;
}

5) 높이 구하기

 이진 트리의 높이를 구하는 함수이다. 트리의 높이를 구하는 방식은 현재 노드 기준 서브 트리의 높이 +1 을 해주는 것이다. 이때 왼쪽 서브 트리와 오른쪽 서브 트리의 높이를 각각 구하고 더 큰 서브 트리의 높이를 선택해야한다. 

코드는 다음과 같다.

int getHeight(BinTree *pSource) { // 이진 트리의 높이 구하기 
	int ret = 0;
	if (pSource != NULL) {
		ret = getHeightNode(pSource->pRootNode);
	}
	return ret;
}
int getHeightNode(BinTreeNode *pSource) {
	int ret = 0;
	if (pSource != NULL) {
		if (pSource->pLeftChild == NULL && pSource->pRightChild == NULL) {
			ret = 1;
		}
		else {
			int leftChildHeight = getHeightNode(pSource->pLeftChild);
			int rightChildHeight = getHeightNode(pSource->pRightChild);
			if (leftChildHeight >= rightChildHeight) {
				ret = leftChildHeight + 1;
			}
			else {
				ret = rightChildHeight + 1;
			}
		}
	}
	return ret;
}

BinaryTreeMain.cpp

 실제 함수들을 활용해보자.

#include"bintree.h"
#include"binarytreetraversal.h"
#include"binarytreeop.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);

	}

	int compare = FALSE;
	int count = 0;
	BinTree *pCopyBinTree = NULL; // 복사할 트리 선언
	pCopyBinTree = copyBinTree(pBinTree); // 복사
	printf("기존 트리 전위 순환 방식으로 출력\n");
	PreorderBinTree(pBinTree);
	printf("\n복사 트리 전위 순환 방식으로 출력\n");
	PreorderBinTree(pCopyBinTree);

	compare = equalBinTree(pBinTree, pCopyBinTree); // 동일성 검사
	printf("\n이진 트리 비교 결과:(%d)\n", compare);
	
	count = getNodeCount(pBinTree); // 노드 개수 
	printf("\n이진 트리 노드 개수: %d\n", count);

	count = getLeafNodeCount(pBinTree); // 단말 노드 개수
	printf("\n이진 트리 단말 노드 개수: %d\n", count);

	count = getHeight(pBinTree); // 트리의 높이
	printf("\n이진 트리의 높이: %d\n", count);

	deleteBinTree(pBinTree);
	deleteBinTree(pCopyBinTree);

    return 0;
}

처음 생성된 트리는 다음과 같고

함수 실행 결과는 다음과 같다.