이번 시간에는 자료구조중 하나인 이진트리 순회에 대해 알아보겠습니다!
트리 순회란 트리 구조에서 각각의 노드를 정확히 한 번만 방문하는 과정을 뜻합니다.
여기서 트리..란 무엇이고 노드란 무엇일까요?
트리구조란,
- 원소들 간에 계층 관계를 가지는 계층형 자료구조
- 원소들 간에 1:多 관계를 가지는 비선형 자료구조
- 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조
입니다.
트리구조와 그래프를 헷갈릴 수 있는데 차이점은 다음과 같습니다.
위의 그림이 트리구조인데, 그래프와 다른점은 Cycle을 갖지 않는다는 점입니다!
위의 그림에서 Cycle을 갖는다면 이는, 그래프 자료구조라고 할 수 있습니다.
노드란,
트리의 원소를 의미합니다.
위와 같은 그림에서 1, 2, 3, 4, 5, 6, 7 모두 노드입니다.
그렇다면.. 이진트리란 무엇일까요?
이진트리란,
- 모든 node의 차수가 2보다 작거나 같은 tree
- 모든 node가 2 이하의 child를 갖는 tree입니다..
여기서 차수란, 노드에 연결된 자식 노드의 수를 의미합니다. 위의 그림에서
1의 차수는 2입니다.(2, 3 노드를 가지므로)
2의 차수는 1입니다.(5 노드를 가지므로)
4의 차수는 0입니다(자식 노드가 없으므로)
여기까지 트리의 개념정리를 완료했습니다.. 그렇다면 대표적인 이진트리의 그림을 알아보겠습니다.
위의 그림은 각각의 모든 노드가 2이하의 child 노드를 가지므로 이진트리라고 할 수 있습니다.
그렇다면 전위 순회, 중위 순회, 후위 순회란 무엇일까요?
알기전에 순회에 대한 개념정리를 하고 넘어가겠습니다.
트리 순회란?
계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산입니다.
순회를 위해 수행할 수 있는 작업에는
1. 현재 노드를 방문하여 데이터를 읽는 작업
2. 현재 노드의 왼쪽 서브트리로 이동하는 작업
3. 현재 노드의 오른쪽 서브트리로 이동하는 작업
이렇게 3가지가 있습니다!
간단하게 전위 순회는 1 -> 2 -> 3의 작업을 수행합니다.
간단하게 중위 순회는 2 -> 1 -> 3의 작업을 수행합니다.
간단하게 후위 순회는 2 -> 3 -> 1의 작업을 수행합니다.
즉. 현재 노드를 먼저 방문할 것인지에 따라 전위, 중위, 후위로 나누는 것입니다.
전위 순회, 중위 순회, 후위 순회에 대해 예시를 통해 알아보겠습니다.
위와 같은 그림에서
전위 순회를 진행한다면, 순서는 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7입니다.
중위 순회를 진행한다면, 순서는 4 -> 2 -> 5 -> 1 -> 6 -> 3-> 7입니다.
후위 순회를 진행한다면, 순서는 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1입니다.
이런 전위 순회, 중위 순회, 후위 순회를 자바 언어로 표현한다면 그 내부 동작은 어떻게 진행될까요?
위의 그림은 전위순회 코드입니다. 이런 전위순회 코드가 작동할때 내부 스택 프레임은 어떻게 순차적으로 진행되는지에 대해 알아보겠습니다.
스택 프레임이란 무엇일까요?
함수가 호출되면 스택에 함수의 매개변수, 호출이 끝난 뒤 돌아갈 복귀 주소값, 함수의 지역변수 등이 저장됩니다. 이렇게 스택에 차례대로 저장되는 함수의 호출 정보를 스택 프레임이라고 합니다.
자기 자신을 호출하는 함수인 재귀함수가 동작할 때는 함수의 지역변수, 매개변수, 복귀 주소 등이 저장되는 공간인 스택 프레임을 이용해 이루어집니다.
전위 순회 스택 프레임 동작
1. 메인함수에서 tree.dfs(tree.root); 코드를 통해 스택에 정보가 저장됩니다.
위의 그림과 같이 저장되는데 dfs는 함수이름, 100은 매개변수인데, 매개변수는 Root 객체이므로 주소값이 저장됩니다. 따라서 루트1의 주소는 편의상 100번지라고 가정하겠습니다. 18번라인은 18번라인까지 수행하고 함수가 끝난 뒤 돌아올 복귀주소를 의미합니다.
System.out.print에 의해 1이 출력되고 18번라인까지 함수가 수행됩니다.
2. 두번째 함수 호출
dfs(200)이 호출되고 if문안에 들어가지 않고 else문에 들어가고, 2를 출력하고 18번째 라인에서 다음함수인 dfs(300)를 실행합니다.
dfs(200)도 마찬가지로 함수안에서 함수를 호출하므로 끝나지 않고 스택 프레임에 저장됩니다.
3. 세번째 함수 호출
여전히 dfs(400)에서는 if문안에 들어가지 않습니다. 4를 출력하고 또한번 함수를 호출합니다. dfs(null)이 때 매개변수가 null인 이유는, 주소값 400번인 노드의 왼쪽 자식이 존재하지 않기때문입니다.
4. 네번째 함수 호출
네번째 함수 호출인 dfs(null)에서 if문을 타고 들어가 return;에 의해 함수가 종료됩니다. 이때 스택프레임에서는 pop이 됩니다.
5. 다섯번째 함수호출
스택프레임에서 팝이되고 난 이후에 dfs(400) 18번라인으로 돌아와 19번라인을 진행하고 마찬가지로 dfs(null)은 함수를 반환합니다. 이후 dfs(400)은 pop됩니다.
6. dfs(400) pop된 이후 스택프레임
7. dfs(200)의 18번라인으로 돌아옴
dfs(200)의 18번라인으로 돌아와 19번라인을 실행합니다. 이후 dfs(500) 이 호출됩니다. dfs(500)에서는 5를 출력하고
또한번 18번라인에서 dfs(null)호출, 19번라인에서 dfs(null)을 호출해 스택프레임에 쌓였다 pop됩니다.
8. dfs(500) 종료
dfs(500)가 종료된뒤 dfs(200)의 19번라인으로 돌아와 20번라인 이후를 수행합니다.
dfs(200)함수가 종료됩니다.
9. dfs(100) 18번라인으로 복귀
dfs(100)의 18번라인으로 복귀한뒤, 19번라인을 수행하고 이때 또 한번의 함수호출 dfs(300)이 진행됩니다.
10. 이후 과정은 전에 진행했던 과정과 동일합니다.
즉, 전위 순회는 현재까지 1 2 4 5가 수행되었고 1의 오른쪽 서브트리도 위와 동일한 과정으로 진행합니다.
정리하자면, 전위 순회는
다음과 같이 출력됨을 확인할 수 있습니다.
그렇다면 중위 순회, 후위 순회는 어떻게 코드를 짜야할까요?
중위 순회 코드
후위 순회 코드
위와 같이 출력을 함수호출 전, 중간, 후 중에 언제할 것이냐에 따라 전위 순회, 중위 순회, 후위 순회가 구별되는 것을 확인할 수 있습니다.
재귀 호출에 의한 스택 프레임의 이해는, DFS나 백트래킹 등과 같은 알고리즘 문제들을 풀기 위해 무엇보다 중요한 개념이니 확실하게 이해하고 넘어가도록 합니다!!
