HW10

1. 첨부의 코드를 이해하고, 첨부 코드를 이용해 BinSrchTree 클래스의 search 함수를 구현하세요(주석 표기된 부분).

2. 1번을 수행한 뒤, 교재 9장 프로그래밍 프로젝트 1번 중 하나인 getHeight 함수(트리의 높이를 구하는 함수)를 구현하세요. 트리의 높이에 대한 정의는 교재의 정의를 따라도 되고, 다른 정의를 따라도 됩니다.

1번과 2번에 구현한 search 함수, getHeight 함수의 코드를 본인 블로그에 업로드하고, 블로그 주소를 제출합니다.

1번 풀이

BinaryNode* BinSrchTree::search(BinaryNode* n, int key) {
	if (n == NULL) return NULL; //아무것도 가리키고 있지 않다는 뜻 
	if (key == n->getData())return n; //현재 노드의 값이 키값과 같으면 n을 반환
	else if (key < n->getData()) //키값이 현재 노드의 값보다 작으면 왼쪽으로
		return search(n->getLeft(), key);
	else return search(n->getRight(), key);
}

2번 풀이

	int getHeight() { return isEmpty() ? 0 : getHeight(root); } //비어있지 않으면 트리의 높이를 구하라
	int getHeight(BinaryNode* node) {
		if (node == NULL) return 0; // 노드가 null을 가리킨다면 0을 반환
		int hLeft = getHeight(node->getLeft());
		int hRight = getHeight(node->getRight());
		return (hLeft > hRight) ? hLeft + 1 : hRight + 1; //recursion으로 들어가서 leaf노드일때부터 +1을 하게 된다
	}