이진트리 순회(깊이우선탐색)

이진트리 순회(깊이우선탐색)

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1

---

전위 순회

def DFS(v):
    if v>7:
        return
    else:
        print(v) # 본래 함수의 일을 먼저 한다. 전위순회
        DFS(v*2)
        DFS(v*2+1)


if __name__=="__main__":
    n = int(input())
    DFS(n)

 

---

중위 순회

def DFS(v):
    if v>7:
        return
    else:
        DFS(v*2)
        print(v) # 본래 함수의 일을 중간에 한다. 중위순회
        DFS(v*2+1)


if __name__=="__main__":
    n = int(input())
    DFS(n)

---

후위 순회

def DFS(v):
    if v>7:
        return
    else:
        DFS(v*2)
        DFS(v*2+1)
        print(v) # 본래 함수의 일을 마지막에 한다. 후위순회


if __name__=="__main__":
    n = int(input())
    DFS(n)

 

스택

D(8)-종료

D(4)-6라인

D(2)-6라인

D(1)-6라인

 

스택 프레임이 어떻게 쌓이는지 생각해보기