트리(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)

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

완전 이진 트리(complete binary tree)

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

편향 이진 트리(skewed binary tree)

• 왼쪽이나 오른쪽 서브 트리만 가지는 트리
• 노드 개수는 높이와 같음
• 메모리 공간이 낭비되고 성능에 문제 발생 ($log_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);
}

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