이진 트리 배열의 DFS - 3

이진 트리 배열에서의 BFS 와 DFS (without stack and recursion)

이진 트리 배열에서의 BFS는 간단합니다. 이진 트리 배열에서 각 요소들이 레벨별로 배치되어 있고, BFS도 레벨별로 검사를 확인하기 때문에, 이진 트리 배열에서의 BFS는 Linear Search(선형검색)과 동일합니다. 

public int bfs(Predicate<T> predicate) {
	for(int i = 0; i < array.length; i++) {
    	if( array[i] != null && predicate.test(array[i])) return i;
    }
    return -1;
 }

 

깊이 우선 탐색(Depth-first Search)는 조금 더 어렵습니다.

 

스택 자료구조를 사용해서 DFS를 하게되면, 일반적인 이진트리에 적용하는 것과 같습니다, 그냥 스택에 인덱스를 넣어주면 됩니다. (https://younghwi.tistory.com/2 참고)

재귀를 이용해서 만드는것도, 스택대신에 재귀함수를 넣어주면 됩니다.