[C언어] 포인터를 이용한 이진 트리(Binary Tree) 구현 & 순회

hhkim·2022년 4월 3일
0

자료구조 스터디

목록 보기
9/10
post-thumbnail

트리(Tree)

  • 노드(Node) + 간선(Edge)
  • 계층 구조: 부모-자식 관계

용어

트리에서의 위치에 따라

  • 루트(root) 노드: 최상위 노드
  • 단말(말단, terminal) 노드 / 잎(leaf) 노드: 자식 노드가 없는 노드
  • 내부(internal) 노드: 자식이 1개 이상 있는 노드

노드 사이의 관계 관점에서

  • 부모(parent) 노드: 어떤 노드의 직접적인 상위 노드
  • 자식(child) 노드: 어떤 노드의 직접적인 하위 노드
  • 선조(ancestor) 노드: 어떤 노드의 상위 노드들
  • 후손(descendent) 노드: 어떤 노드의 하위 노드들
  • 형제(sibling) 노드: 같은 부모를 갖는 노드

속성 관점에서

  • 레벨(level): 루트 노드로부터의 거리 (루트 노드의 경우 레벨이 1)
  • 높이(height): 단말 노드로부터의 최대 거리 (단말 노드의 경우 높이가 1)
    • 트리의 높이는 루트 노드의 높이를 말함
  • 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 차수(degree): 자식 노드의 개수

기타

  • 서브트리(subtree): 전체 트리의 부분집합
  • 포리스트(forest): 트리들의 집합

이진 트리 (Binary Tree)

최대 차수가 2인 트리

  • 서브 트리 간 순서가 존재

포화 이진 트리(full binary tree)

  • 각 레벨에 노드가 꽉 찬 이진 트리
  • 각 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있으며, 부여된 번호는 항상 일정
  • 트리의 높이가 hh일 때 노드의 개수는 2h12^h - 1

완전 이진 트리(complete binary tree)

  • 높이가 hh일 때, 레벨 11부터 h1h-1까지는 포화 이진 트리
  • 마지막 레벨 hh에서는 왼쪽부터 오른쪽으로 순서대로 채워진 이진 트리
  • 중간에 빈 곳이 있으면 안 됨

편향 이진 트리(skewed binary tree)

  • 왼쪽이나 오른쪽 서브 트리만 가지는 트리
  • 노드 개수는 높이와 같음
  • 메모리 공간이 낭비되고 성능에 문제 발생 (log2nlog_2n의 탐색 시간을 보장받지 못함)

이진 트리 구현

포인터를 이용한 구현

구조체와 함수 원형

typedef struct BinTreeNodeType
{
	char					data;
	struct BinTreeNodeType*	pLeftChild;
	struct BinTreeNodeType*	pRightChild;
}	BinTreeNode;

typedef struct BinTreeType
{
	struct BinTreeNodeType*	pRootNode;
}	BinTree;

BinTree*		makeBinTree(BinTreeNode rootNode);
BinTreeNode*	getRootNodeBT(BinTree* pBinTree);
BinTreeNode*	insertLeftChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode*	insertRightChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode*	getLeftChildNodeBT(BinTreeNode* pNode);
BinTreeNode*	getRightChildNodeBT(BinTreeNode* pNode);
void			deleteBinTree(BinTree** pBinTree);
void			deleteBinTreeNode(BinTreeNode* pNode);

이진 트리 생성

BinTree	*makeBinTree(BinTreeNode rootNode)
{
	BinTree	*tree;

	tree = (BinTree *)calloc(1, sizeof(BinTree));
	if (tree == NULL)
		return (NULL);
	tree->pRootNode = (BinTreeNode *)calloc(1, sizeof(BinTreeNode));
	if (tree->pRootNode == NULL)
	{
		free(tree);
		return (NULL);
	}
	*(tree->pRootNode) = rootNode;
	return (tree);
}

자식 노드 추가

BinTreeNode	*insertLeftChildNodeBT(BinTreeNode *pParentNode, BinTreeNode element)
{
	if (pParentNode == NULL)
	{
		fprintf(stderr, "ERROR: 트리 없음\n");
		return (NULL);
	}
	pParentNode->pLeftChild = (BinTreeNode *)calloc(1, sizeof(BinTreeNode));
	if (pParentNode->pLeftChild == NULL)
	{
		fprintf(stderr, "ERROR: 노드 메모리 할당 X\n");
		return (NULL);
	}
	*(pParentNode->pLeftChild) = element;
	return (pParentNode->pLeftChild);
}

BinTreeNode	*insertRightChildNodeBT(BinTreeNode *pParentNode, BinTreeNode element)
{
	if (pParentNode == NULL)
	{
		fprintf(stderr, "ERROR: 트리 없음\n");
		return (NULL);
	}
	pParentNode->pRightChild = (BinTreeNode *)calloc(1, sizeof(BinTreeNode));
	if (pParentNode->pRightChild == NULL)
	{
		fprintf(stderr, "ERROR: 노드 메모리 할당 X\n");
		return (NULL);
	}
	*(pParentNode->pRightChild) = element;
	return (pParentNode->pRightChild);
}

자식 노드 반환

BinTreeNode	*getLeftChildNodeBT(BinTreeNode *pNode)
{
	if (pNode == NULL)
	{
		fprintf(stderr, "ERROR: 노드 없음\n");
		return (NULL);
	}
	return (pNode->pLeftChild);
}

BinTreeNode	*getRightChildNodeBT(BinTreeNode *pNode)
{
	if (pNode == NULL)
	{
		fprintf(stderr, "ERROR: 노드 없음\n");
		return (NULL);
	}
	return (pNode->pRightChild);
}

이진 트리 삭제

  • 후위 순회로 각 노드를 삭제 (L-R-V)
void	deleteBinTree(BinTree **pBinTree)
{
	if (pBinTree == NULL || *pBinTree == NULL)
	{
		fprintf(stderr, "ERROR: 트리 없음\n");
		return ;
	}
	deleteBinTreeNode((*pBinTree)->pRootNode);
	free(*pBinTree);
	*pBinTree = NULL;
}

void	deleteBinTreeNode(BinTreeNode *pNode)
{
	if (pNode == NULL)
		return ;
	deleteBinTreeNode(pNode->pLeftChild);
	deleteBinTreeNode(pNode->pRightChild);
	free(pNode);
}

이진 트리 순회(traversal)

  • 루트 노드를 언제 순회하느냐가 기준
  • 재귀를 이용하여 구현
  • 전위 순회: A B D H I E J C F K G L M
  • 중위 순회: H D I B J E A F K C L G M
  • 후위 순회: H I D J E B K F L M G C A

함수 원형

void	preorderTraverse(BinTreeNode *pNode);
void	inorderTraverse(BinTreeNode *pNode);
void	postorderTraverse(BinTreeNode *pNode);

V: visited, L: left, R: right

전위 순회(preorder traversal)

  • V-L-R
void	preorderTraverse(BinTreeNode *pNode)
{
	if (pNode == NULL)
		return ;
	printf("%c ", pNode->data);
	preorderTraverse(pNode->pLeftChild);
	preorderTraverse(pNode->pRightChild);
}

중위 순회(inorder traversal)

  • L-V-R
void	inorderTraverse(BinTreeNode *pNode)
{
	if (pNode == NULL)
		return ;
	inorderTraverse(pNode->pLeftChild);
	printf("%c ", pNode->data);
	inorderTraverse(pNode->pRightChild);
}

후위 순회(postorder traversal)

  • L-R-V
void	postorderTraverse(BinTreeNode *pNode)
{
	if (pNode == NULL)
		return ;
	postorderTraverse(pNode->pLeftChild);
	postorderTraverse(pNode->pRightChild);
	printf("%c ", pNode->data);
}

🔗 포인터를 이용한 이진 트리 전체 코드

0개의 댓글