viewimage.php?id=3dafdf21f7d335ab67b1d1&no=24b0d769e1d32ca73dec84fa11d0283195504478ca9b7677dc322c30ca359b4576cb00ea8b10e5bfa44526b406ceaae549acc74ce53fb51a81b721370001ee26251cc6e42007






완전이진트리와 순회 개념설명


viewimage.php?id=3dafdf21f7d335ab67b1d1&no=24b0d769e1d32ca73dec84fa11d0283195504478ca9b7677dc322c30ca359b4576cb00ea8b10e5bfa44526b406cec78947e719482d8466b31d7a81101eca838b0a4fe6371604f5




완전이진트리의 장점은 입력,삭제,추가의

시간복잡도가 모두 O(logn)이다


루트, 오른쪽 서브트리, 왼쪽 서브트리, 레벨을 알면 사용할 수 있다


완전이진트리에서의 깊이우선탐색 방법은

스택과 재귀 두가지가 있는데

굳이 스택 자료구조를 통해 구현하기보다


재귀함수를 통해

언어 내부의 스택프레임을

사용하는것이 더 빠르다


순회는 다른 자료구조에서는 주로 전위순회를 하지만

병합정렬에서는 후위순회를 사용한다


트리를 탐색할때 전위순회방식은

루트노드에서 출발해서 왼쪽과 오른쪽 중에


왼쪽으로 말단노드까지 깊이를 우선으로 탐색하고

다시 이전레벨에서 찾지 않은 노드가 있다면

백트래킹 해서 다시 탐색하는것을 반복하는것을 통해 모든 루트를 탐색한다


전위,중위,후위 모두

왼쪽으로 탐색하는것은 똑같지만 차이가 있다

예를들면 재귀함수 각각의 자신의 기능이

자신의 위치를 출력하는것이라면

방문하는것과 출력하는것은 차이가 있다


방문하는것이 함수를 호출하고 대기하는것이라면

출력하는것은 자신을 실행하는것이다


재귀함수로 DFS를 하는 방식을 알려면

출력이라는 결과보다

함수의 호출순서를 알아보는것을 이해해야한다


전위순회방식 부모-왼쪽서브트리-오른쪽서브트리

전위순회방식은 함수 자신의 일을 먼저 수행하고

다음노드로 이동하는것을 말하고

1 2 4 5 3 6 7 형태가 된다


중위순회방식 왼쪽서브트리-부모트리-오른쪽서브트리

중위순회방식은 부모 왼쪽 오른쪽으로 출력하는것을 말하고

4 2 5 1 6 3 7이 된다



후위순회방식 왼쪽서브트리-오른쪽서브트리-부모트리

중위순회방식은 부모 왼쪽 오른쪽으로 출력하는것을 말한다

4 5 2 6 7 3 1이 된다


숫자 규칙


viewimage.php?id=3dafdf21f7d335ab67b1d1&no=24b0d769e1d32ca73dec84fa11d0283195504478ca9b7677dc322c30ca359b4576cb00ea8b10e5bfa44526b406cec78947e719482d8466b31d7a814549cc848bdf1ee8a5e47d89


다시 이 표를 보면 부모노드와 자식노드의 관계는 항상

왼쪽은 부모노드*2 오른쪽은 부모노드*2+1이다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

문제풀기


재귀함수를 이용한 깊이우선탐색


viewimage.php?id=3dafdf21f7d335ab67b1d1&no=24b0d769e1d32ca73dec84fa11d0283195504478ca9b7677dc322c30ca359b4576cb00ea8b10e5bfa44526b406ceaae549acc74ce53fb51a81b7726c0101b62653568e99d5a0

이 함수가 실행되는 순서


첫번째 1을 받고 DFS(1)의 7라인으로 들어간다

두번째 1에 2를 곱해서 DFS(2)의 7라인으로 들어간다

세번째 2에 2를 곱해서 DFS(4)의 7라인으로 들어간다

네번째 4에 2를 곱해서 DFS(8)에 들어갔다가 조건문에 걸려서 스택이 빠지고 DFS(4)로 복귀한다

다섯번째 DFS(4)의 8라인으로 들어간다

여섯번째 4*2+1을 해서 DFS(9)에 들어갔다가 조건문에 걸려서 스택이 빠지고 DFS(4)로 복귀한다

일곱번째 DFS(4)의 9라인에서 4가 출력되고 스택이 빠지고 DFS(2)로 복귀한다

여덟번째 DFS(2)의 8라인으로 들어간다

아홉번째 2*2+1을 해서 DFS(5)에 들어간다

열번째 DFS(5)에서도 7라인 5*2 8라인 5*2+1이 되고 스택이빠지고 DFS(5)로 복귀한뒤 5를 출력한다

열한번째 DFS(5)의 스택프레임이 빠지고 DFS(2)의 9라인에서 2를 출력한다

열두번째 DFS(1)의 8라인으로 들어간다

열세번째 1*2+1을 해서 DFS(3)으로 들어간다

열네번째 DFS(3)의 7라인으로 들어간다

열다섯번째 3*2를 해서 DFS(6)으로 들어간다

열여섯번째 7라인에서 6*2 8라인에서 6*2+1로 DFS(12), DFS(13)에 들어갔다가 조건문을 만나 스택프레임이 빠진다

열일곱번째 DFS(6)의 9라인으로 돌아와서 6을 출력한다

열여덟번째 DFS(6)의 스택프레임이 빠지고 DFS(3)으로 돌아온다

열아홉번째 DFS(3)의 8라인으로 들어간다

스무번째 3*2+1을 해서 DFS(7)로 들어간다

스물한번째 DFS(7)에서 7라인 7*2 8라인 7*2+1을 통해 DFS(14), DFS(15)에 들어갔다가 조건문을 만나 스택프레임이 빠진다

스물두번째 DFS(7)의 9라인에서 7을 출력한다

스물세번째 DFS(7)의 스택프레임이 빠지고 DFS(3)의 9라인에서 3을 출력한다

스물네번째 DFS(3)의 스택프레임이 빠지고 DFS(1)의 9라인에서 1을 출력한다


꿈★은 이루어진다

내일채움공제 되는 중소기업 가자 화이팅!