[백준]알고리즘_이진트리순회(백준1991번)
이진트리 순회 - DFS
깊이 우선 탐색은 리프토드까지 아래로 내려가면서 탐색함. 더 이상 탐색할 곳이 없으면 부모에게 돌아감!
종류
1) 전회 순회(preorder) 노드방문 > 왼쪽자식>오른쪽자식
예시 : A > B > D > H > E > I > J > C > F >G
사진 설명을 입력하세요.
2) 중위 순회(inorder) 왼쪽자식 > 노드방문 > 오른쪽자식
예시 : H > D > B > I > E >J > A > F> C > G
사진 설명을 입력하세요.
3) 후위 순회(postorder) 왼쪽자식 > 오른쪽자식 > 노드방문
예시 : H > D > I > J > E > B > F > G > C > A
백준_1991번
정답
생각한 슈도코드
MAIN
이진트리 배열 선정.
Char at> 문자를 숫자로 변형해주는 거. node에 각각 left/right 순서대로 넣음
DFS(node) >> DFS(0) DFS(1) / DFS(2) 호출
>> dfs(node) : 전위순회 . 노드 기준으로 왼쪽 tree[node][0] : 중위순회
노드 기준으로 오른쪽 tree[node][1] : 후위순회
방문(전위/중위/후위) 함수 만들기
preorder / inorder/ postorder
각각 탐색진행에 맞게 탐색해주고 예외값 처리해주기
ex) predorder
static void preorder(int newNode){
System.out.println((char)nowNode + 65); //노드방문
preorder(tree[newNode][0]; // 왼쪽노드 방문
preorder(tree[newNode][1]; // 오른쪽노드 방문
*예외처리 : -19(말단 노드) 일떄는 / 현재값 -1일때 그냥 return
정답
MAIN
전위 중위 후위 구현
사진 설명을 입력하세요.
사진 설명을 입력하세요.
백준 어지쩌지 성공...!! 다시 하라고 하면 또 못하게씾 하ㅏㅏㅏㅏㅏㅏㅏㅏㅏ너무헤갈
일단 main에서 알파벳을 index로 구현해오는 과정이 너무 어려웠다
이진트리 순회 - BFS
너비 우선 탐색은 낮은 레벨(높이)에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다가
한 레벨에서 탐색이 끝나면 다음 레벨로 내려감.
위의 트리를 예씨로 하면 A>B>C>D>E>F>G>H>I>j 순서대로 간다고 생각하면 됨.
자바에서는 보통 큐로 구현을 많이 함.
Queue<Int> que //큐 구현
que.add(root) //root 에 있는 값 추가
while(!que.isEmpty){ //큐에 아무것도 없을때까지 돌려버림
node = que.poll() //값을 빼서 지금 node 확인
for(nextnode:인접리스트) //확인 후 인접한거 넣어버리기
que.add(nextnode)
}
#백준 1991번(동일한 문제를 bfs로 구현하기)
사진 설명을 입력하세요.
이진탐색 정리 끝~~~~~~~~~~~
남들이 오전에 이해한 걸 방금 구현하느라 조금 자괴감이 드는데 어쪄겠어 뭐!!!!!!!! 일단 해냈으니 됐당ㅇㅇ
이제 그래프 공부를 다시 해보겠다ㅏ