🔧변경내용🔨
제목 날짜 내용 발행일 23.03.15
📌들어가기에 앞서
해당 포스터는 자료구조 학습 내용 중
Tree Traversal기초이론에 대한 내용을 정리한 것입니다.
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
트리 구조는 계층적 구조라는 특별한 특징을 가진다.
모든 노드를 순회하는 방법엔 크게 세 가지가 있다.
트리를 순회할 수 있는 세 가지 방법은
1) 전위 순회
2) 중위 순회
3) 후위 순회
이 순회 방식들은 모두 노드를 순회할 때 왼쪽부터 오른쪽으로 조회한다는 공통점이 있다.
📖 전위 순회 (preorder traverse)
Root => Left => Right
-
전위 순회에서 가장 먼저 방문하는 노드는
루트 -
루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색
-
즉 부모 노드가 제일 먼저 방문 되는 순회 방식
-
전위 순회는 주로
트리를 복사할 때 사용
📖 중위 순회 (inorder traverse)
Left => Root => Right
-
중위 순회는 루트를 가운데에 두고 순회
-
제일 왼쪽 끝에 있는 노드부터 순회하기 시작
-
루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색
-
부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식
-
중위 순회는 이진 탐색 트리의
오름차순으로 값을 가져올 때 사용
📖 후위 순회 (postorder traverse)
Left => Right => Root
-
후위 순회는 루트를 가장 마지막에 순회
-
제일 왼쪽 끝에 있는 노드부터 순회하기 시작
-
루트를 거치지 않고 오른쪽으로 이동해 순회
-
제일 마지막에 루트를 방문
-
후위 순회는
트리를 삭제할 때사용- 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문
📖 레벨 순회 (levelorder traverse)
-
레벨 순회는 루트를 방문하는 기준으로 순회를 하는 것이 아닌 트리의
레벨 기준으로 노드들을 방문하는 순회 방법 -
루트 노드를 시작으로 아래로 뻗어나가며 노드들을 방문하며 루트 노드의 레벨이 1레벨이라고 했을 때 아래로 내려갈수록 레벨은 증가하는 특징을 보인다.
-
동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문
📖 순회 방식을 나누는 이유
-
이진 트리 탐색의 경우는 간단한 편이지만 순회 방법은 조금 복잡한 편
-
일정 조건에 의해 설계된 트리 구조는 자식 노드에 대한 조건이 명확하다면 원하는 값을 쉽게 찾아낼 수 있게 되지만,
- 트리 구조 전체를 탐색할 때는 이야기가 조금 달라지기 때문
-
모든 노드를 방문하기 위해서는 일정한 조건이 필요하고,
- 트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의는 필수적으로 필요
📚 레퍼런스
코드스테이츠 수업자료
