[C언어] Binary Tree (4) - sumOfOddNodes 함수 구현하기

Binary Tree (4) - sumOfOddNodes 함수 구현하기

홀수 값 노드들의 합을 구하는 함수

주어진 요소 확인하기

구조체

• BTNode: (struct) 이진 트리 노드 구조체
  • item: (int field) 노드의 값
  • *left: (pointer field) 왼쪽 자식 노드 주소
  • *right: (pointer field) 오른쪽 자식 노드 주소

• StackNode: (struct) 트리 생성을 위한 스택 노드 구조체
  • *btnode: (pointer field) 이진 트리 노드 주소
  • *next: (pointer field) 다음(스택 아래쪽) 노드 주소

• Stack: (struct) 트리 생성을 위한 스택 구조체
  • *top: (pointer field) 스택 최상단 노드의 주소

sumOfOddNodes 함수의 매개 변수

• *node: (pointer) 이진 트리 루트 노드 주소

 

핵심 아이디어

• 각 노드에 재귀적으로 홀수값을 가지는지 검사
  • 노드가 NULL인 경우 0을 반환
  • 노드의 값이 홀수인 경우 해당 값 합산
  • 좌우 서브트리에서 얻은 결과를 합산하여 반환

 

구현하기

int sumOfOddNodes(BTNode *node) {
	// 노드가 없으면 0 반환
	if (node == NULL) return 0;
	
    // 왼쪽 서브트리의 홀수 합
	int left = sumOfOddNodes(node->left);
	// 오른쪽 서브트리의 홀수 합
	int right = sumOfOddNodes(node->right);
	
	// 현재 노드의 값이 홀수면 현재 값도 합산해 반환
	if (node->item % 2 == 1) {
		return node->item + left + right;
	}
	// 짝수면 자식 노드들의 결과만 합산해 반환
	return left + right;
}