[자료구조] 이진 트리의 여러가지 연산

이진 트리의 여러가지 연산

이진 트리를 활용하기 위해서는 여러가지 연산이 필요합니다. 예를 들어, 단말 노드의 개수만 구해야 하는 상황이 존재하거나 모든 데이터의 합, 최솟값을 구해야 하는 상황 등이 있습니다. 

 

이진 트리를 활용하기 위해 사용할 수 있는 여러가지 연산에 관한 알고리즘을 작성해보았습니다.

 

트리에 존재하는 모든 노드의 개수 구하기

각각의 서브트리에 대하여 순환 호출한 다음 반환값에 1을 더하여 반환합니다.

int get_node_count(TreeNode *node)  {
	int count=0;
	if( node != NULL )
		count = 1 + get_node_count(node->left)+ get_node_count(node->right);
	return count;
}

 

트리의 높이 구하기

서브트리에 대하여 순환호출한다음 서브트리들의 반환값 중에서 최댓값을 구하여 1을 더한 후 반환합니다.

int get_height(TreeNode *node)  {
	int height=0;
	if( node != NULL )
		height = 1 + max(get_height(node->left), get_height(node->right));
	return height;
}

 

트리의 단말 노드 개수 구하기

int get_leaf_count(TreeNode *node)
{
	int count = 0;

	if (node != NULL) {
		if (node->left == NULL && node->right == NULL)
			return 1;
		else
			count = get_leaf_count(node->left) + get_leaf_count(node->right);
	}
	return count;
}

 

트리의 비단말 노드 개수 구하기

L트리와 R트리가 존재하면 1을 카운트하고 재귀형으로 다시 호출한 값을 카운트합니다.

int numOfNonTerminals(TreeNode* node) {
	int count = 0;
	if (node == NULL) {
		return 0;
	}
	else if (node->left == NULL && node->right == NULL) {
		return 0;
	}
	else {
		count += 1 + numOfNonTerminals(node->left) + numOfNonTerminals(node->right);
	}
	return count;
}

 

두 트리가 동일한 트리인지 판단하기

가장 먼저 트리1과 트리2가 NULL인지를 확인합나다. NULL이 아니면서 데이터가 각각 존재하고 트리1과 트리2의 L트리와 R트리를 재귀형으로 다시 호출하여 참이 나오는 조건을 모두 만족하면 1을 반환하고 그렇지 않으면 0을 반환합니다.

int isEqual(TreeNode* node1, TreeNode* node2) {
	if ((node1 == NULL && node2 == NULL) || (node1 != NULL && node2 != NULL && (node1->data == node2->data) && isEqual(node1->left, node2->left) &&
		isEqual(node1->right, node2->right))) {
		return 1;
	}
	else {
		return 0;
	}
}

 

트리에 존재하는 데이터 중 최솟값 구하기

int* min_val(TreeNode* p) {
	if (p == NULL) {
		int temp = INT_MAX;
		return &temp;
	}
	int* min = &(p->data);
	if (*min > *(min_val(p->left))) min = min_val(p->left);
	if (*min > *(min_val(p->right))) min = min_val(p->right);
	return min;
}

 

트리가 균형 트리(Balanced Tree)인지 판단하기

균형 트리(balanced tree)란, 어떤 트리를 선택하여도 그 트리의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이의 차이가 1이하인 트리를 말합니다.

L트리와 R트리의 height 차이가 1이상이면 0을 반환합니다. 자식 트리가 NULL인 경우 get_height함수는 0을 반환하므로 높이 차이가 1초과인지 아닌지를 검사할 수 있습니다.

int get_height(TreeNode* node)
{
	int height = 0;
	if (node != NULL)
		height = 1 + max(get_height(node->left), get_height(node->right));
	return height;
}
int isBalanced(TreeNode* node)
{
	int b;
	if (node == NULL) return 1;
	b = get_height(node->left) - get_height(node->right);
	if (b > 1 || b < -1)
		return 0;
	else
		return (isBalanced(node->left) && isBalanced(node->right));
}

 

트리에 존재하는 모든 데이터의 합 구하기

노드의 데이터와 L트리, R트리를 재귀형으로 호출하여 모든 노드를 방문하여 발견한 데이터를 모두 저장합니다.

int get_sum(TreeNode* node) {
	int sum = 0;
	if (node != NULL) {
		sum += node->data + get_sum(node->left) + get_sum(node->right);
	}
	return sum;
}

 

자식 노드가 하나만 존재하는 트리의 개수 구하기

L트리와 R트리가 NULL인 경우(자식 서브트리가 없는 경우) 0을 반환하고 L트리만 있거나 R트리만 있는 경우 1을 추가하고 그 트리의 서브트리를 재귀형으로 다시 호출합니다. L트리와 R트리가 모두 있는 경우 카운트하지 않고 서브트리를 재귀형으로 호출한 결괏값을 각각 더합니다.

int havingOneChild(TreeNode* node) {
	if (node == NULL)
		return 0;
	else if (node->left == NULL && node->right == NULL)
		return 0;
	else if (node->left == NULL && node->right != NULL)
		return 1 + havingOneChild(node->right);
	else if (node->left != NULL && node->right == NULL)
		return 1 + havingOneChild(node->left);
	else if (node->left != NULL && node->right != NULL)
		return havingOneChild(node->left) + havingOneChild(node->right);
	return 0;
}

 

트리에 저장된 데이터 값을 모두 1씩 제거하기

void decrement(TreeNode* node) {
	if (node != NULL) {
		node->data -= 1;
		decrement(node->left);
		decrement(node->right);
	}
}

트리가 NULL이 아니면 데이터를 1제거하고 L트리와 R트리가 존재하면 재귀형으로 다시 호출해서 모든 트리를 방문하여 데이터를 1제거합니다.

 

 

질문 || 해석이 필요하신 분은 댓글로 남겨주시기 바랍니다.