문제 / 이진 트리 순회(깊이 우선 탐색) / Python 파이썬

 

문제 제목: 이진 트리 순회(깊이 우선 탐색)

 

---

개념

• 전위 순회 방식: 함수 출력시 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 출력
• 중위 순회 방식: 함수 출력시 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 출력
• 후위 순회 방식: 함수 출력시 왼쪽 자식 -> 오른쪽 자식 - >부모  순서로 출력

1. 전위 순회 방식

함수 출력시 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 출력

def DFS(v):
    if v>7:
        return
    else:  
        print(v, end=' ')
        DFS(v*2)
        DFS(v*2+1)
        
if __name__=="__main__":
    DFS(1)

2. 중위 순회 방식

함수 출력시 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 출력

def DFS(v):
    if v>7:
        return
    else:  
        DFS(v*2)
        print(v, end=' ')
        DFS(v*2+1)
        
if __name__=="__main__":
    DFS(1)

 

3. 후위 순회 방식

함수 출력시 왼쪽 자식 -> 오른쪽 자식 - >부모  순서로 출력

def DFS(v):
    if v>7:
        return
    else:  
        DFS(v*2)
        DFS(v*2+1)
        print(v, end=' ')
        
if __name__=="__main__":
    DFS(1)

대표적으로 병합정렬이 있음

왼쪽 자식 처리 후 오른쪽 자식 처리 후 부모(본인) 처리

이제 더이상 더 갈 수가 없으니 DFS(4)는 pop되어 반환됨 그리고나서 D(5) 순회

 

---

※ 알아야 할 것

- 재귀함수는 모두 DFS라고 칭함. 

 

- 링크 게시글을 모두 이해했으면 쉽게 이 글도 이해할 수 있을 것임

 https://sillon-coding.tistory.com/211

[자료구조] 재귀 함수와 스택 / 파이썬 Python