[자료구조 트리] What is Binary Tree Traversal? / 이진트리 순회란?

이진트리 순회(Binary Tree Traversal)에 대해 알아보자

 

이진트리순회

    - Tree의 각 node를 한 번씩 방문하는 알고리즘

    - 재귀를 사용하는 순회

        - 중위 순회(Inorder Traversal or LVR) : 루트 노드를 중간에

        - 전위 순회(Preorder Traversal or VLR) : 루트 노드를 먼저

        - 후위 순회(Postorder Traversal or LRV) : 루트 노드를 마지막에

    - 반복문을 사용하는 순회

        - Iteractive Inorder Traversal : 반복문을 사용하는 중위 순회 (스택 사용)

        - Level-Order Traversal : 반복문을 사용하는 level order 순회 (큐 사용)

 

중위 순회(Inorder Traversal) LVR

    - 중위 순회의 흐름

출처) 윤성우의 열혈 자료구조

    - 중위 순회 함수 구현

출처) fundamentals of data structures in c - horowitz

    - 중위 순회 코드 실행 따라가기

출처) fundamentals of data structures in c - horowitz

전위 순회(Preorder Traversal) VLR

    - 전위 순회의 흐름

출처) 윤성우의 열혈 자료구조

    - 전위 순회 함수 구현

 

출처) fundamentals of data structures in c - horowitz

    - 전위 순회 코드 실행 따라가기(미완성)

출처) fundamentals of data structures in c - horowitz

후위 순회(Postorder Traversal) LRV

    - 후위 순회의 흐름

출처) 윤성우의 열혈 자료구조

    - 후위 순회 함수 구현

출처) fundamentals of data structures in c - horowitz

    - 후위 순회 코드 실행 따라가기(미완성)

출처) fundamentals of data structures in c - horowitz

Iteractive Inorder Traversal : 반복문을 사용하는 중위 순회 (스택 사용)

    - 중위 순회의 흐름이다

출처) 윤성우의 열혈 자료구조

    - Iteractive Inorder Traversal 함수 구현

출처) fundamentals of data structures in c - horowitz

    - Iteractive Inorder Traversal 코드 실행 따라가기

        OUTPUT = A/B*C*D*E

출처) 경북대 정기숙 교수님 자료구조 강의자료

Level-Order Traversal : 반복문을 사용하는 level order 순회 (큐 사용)

    - 레벨 순으로 순회한다

출처) 경북대 정기숙 교수님 자료구조 강의자료

    - Level-Order Traversal 함수 구현

출처) 경북대 정기숙 교수님 자료구조 강의자료

    - Level-Order Traversal 코드 실행 따라가기

        OUTPUT = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

출처) 경북대 정기숙 교수님 자료구조 강의자료