[JavaScript] 트리 검색 코드 - 재귀호출을 활용하여 트리 구조에서 노드 검색

자바스크립트로 이진 트리가 아닌, 정렬되지 않은 트리를 순차 탐색하는 코드를 구현해 보았다.
재귀호출을 사용해서 트리 구조 전체를 탐색하도록 했고, 자바스크립트만의 특징을 활용해서 구조를 단순화(?) 했다.
탐색하기 위한 트리는 이전에 포스팅했던 트리 생성 루틴을 사용해서 만들었다.

먼저 소스 코드를 확인해보자.


소스 코드

var getNode = function ( _children, _id, _result ) {

	/* 전체 리스트를 탐색 */
	for ( var i=0, child; child = _children[i]; i++ ) {

		/* 노드를 찾았으면, */
		if ( child.id === _id ) {

			/* 결과값 리턴 */
			return child;
		}

		/* 찾는 노드가 아니면, */
		else {

			/* 자식 노드들를 탐색 */
			_result = arguments.callee( child.children, _id ) || _result;
		}
	}

	return _result;
}

보는 것과 같이 매우 단순하게 트리 검색을 구현했다. 여기에서는 id로 찾는 방식을 구현했는데, 다른 것으로 찾고싶다면 적당하게 바꿀 수 있다.

현재 트리 레벨에서 id가 일치하는 노드를 찾고 일치하지 않으면 재귀호출로 자식 노드들을 탐색하게 한다. 재귀 호출을 통해 리턴받은 값이 null이나 undefined 가 아닌 경우에만 _result 변수에 값이 들어가고, 이 값이 최종적으로 리턴된다.

속도측정은 여러 상황에서 해보지 못했지만, 기대했던 속도 이내에 트리 검색을 수행해주었다. (측정되지 않을 정도의 짧은 시간)

jsFiddle을 통해 실제 동작 예를 확인해보자.



트리 검색 샘플




위의 변환된 트리모델에서 아무 id 값을 가져다가 검색할 노드 ID 필드에 넣어주고 검색을 시도하면 결과값이 검색되는 것을 확인할 수 있다.


마치며

너무 단순한 코드지만, 자주 쓰일 때가 많아 정리차원에서 포스팅한다.
자바스크립트를 활용한 노드 검색에 대한 작은 안목이 생기는데 도움이 되었으면 좋겠다.