Stack Frame (스택 프레임)이란?
메모리의 스택 영역은 함수의 호출과 관련된 정보(지역변수, 매개변수 등)를 저장하는 곳이다. 이 곳에 저장되는 함수의 호출 정보를 스택프레임이라고 하며, 호출이 완료되면 해당 스택프레임은 소멸한다. 스택(stack)이라는 자료구조에 맞게 LIFO(Last In First Out)형태로 스택프레임이 쌓이고 소멸한다.
이를 이용해 전위 순회, 중위 순회, 후위 순회를 표현해보자.
순회 종류
- 전위 순회 (prefix) : 부모 - 자식(왼) - 자식(오)
- 중위 순회 (infix) : 자식(왼) - 부모 - 자식(오)
- 후위 순회 (postfix) : 자식(왼) - 자식(오) - 부모
완전 이진트리로 구현하기
코드로 구현하기(js)
- 스택프레임의 원리를 이용하여 재귀함수로 구현해보자. 재귀로 호출된 함수들이 스택프레임에 어떤 상태로 쌓기고 실행되는지를 잘 파악해야한다. 처음 재귀함수를 호출한 함수에 대한 스택프레임은 스택의 가장 밑바닥에서 마지막에 호출되고, 호출될 때는 다른 재귀함수의 호출로 멈췄던 시점(코드 line)부터 이어서 실행한다.
- 재귀함수가 낯설다면 if - else 만 생각하자.
- **if** 에서 언제 이 재귀를 멈출지, 멈추었을 때 어떤 액션을 취할지를 구현
- **else** 에서 어떤 형태로 재귀함수를 쌓아갈지 구현
- 완전 이진트리에서 부모와 자식의 인덱스 관계는 다음과 같다 (시작 노드는 1부터 시작하는게 편함)
- 부모 : n
- 왼쪽 자식 : 2n
- 오른쪽 자식 : 2n + 1
전위 순회
부모 - 왼 - 오
function prefix(n){ let answer=""; function DFS(v){ if(v>7) return; else{ // 부모 - 왼 - 오 answer+=(v+' '); //부모 노드 먼저 answer에 넣기 DFS(v*2); //왼쪽 자식노드가 스택프레임에 먼저 쌓인 후 DFS(v*2+1); //호출이 끝난 후 오른쪽 자식 노드가 스택프레임에 들어간다. } } DFS(n); return answer; }
중위 순회
왼 - 부모 - 오
function infix(n){ let answer=""; function DFS(v){ if(v>7) return; else{ DFS(v*2); //왼쪽 자식 노드 answer+=(v+' '); //부모 노드 DFS(v*2+1); //오른쪽 자식 노드 } } DFS(n) return answer; }
후위 순회
왼 - 오 - 부모
function postfix(n){ let answer=""; function DFS(v){ if(v>7) return; else{ DFS(v*2); //왼쪽 자식 노드 DFS(v*2+1); //오른쪽 자식 노드 answer+=(v+' '); //부모 노드 } } DFS(n) return answer; }
호출
console.log(prefix(1)); console.log(infix(1)); console.log(postfix(1));
참고 링크
[TCP school.com](http://tcpschool.com/c/c_memory_structure#:~:text=메모리의 스택(stack) 영역,이 완료되면 소멸합니다.&text=스택 영역은 메모리의,의 방향으로 할당됩니다.)