[TIL] 자료구조 - 트리:Contains

※ 트리: Contains

- 특정 요소가 트리에 포함되어 있는지 확인하는 함수를 구현하고자 한다면 트리에 새로운 데이터를 추가하는 과정과 유사하게 동작한다.

 

우선 루트에서 시작하여 트리의 규칙을 따라 내려간 뒤 해당 요소를 찾으면 True 반환하고 null 노드에 도달하면 False를 반환한다 이 과정을 코드로 구현하면 다음과 같은데 재귀 함수를 이용해 트리의 규칙을 따라 내려가는 기능을 구현하였다

 

public boolean contains (E obj, Node<E> node){
	// 트리의 끝에 도달했는데 null
    if(node == null)
    	return false;
    // node의 data와 일치
    if(((Comparable<E>)obj).compareTo(node.data)==0)
    	return true;
    // go to the right
    if(((Comparable<E>)obj).compareTo(node.data)>0)
    	return contains(obj, node.right);
    // go to the left
    return contains(obj, node.left);
}