2022/03/28) 3. 이진트리순회 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<이진트리순회>
: 이진트리를 전위순회, 중위순회, 후위순회로 출력해본다.

2. 해결 방법

1. 먼저 부모값이 n이면 왼쪽자식은 nx2 오른쪽자식은 nx2+1이다.
2. 스택프레임 그림 직접 그려서 해본다

! 부모가 기준이다!!! (왼쪽 -> 오른쪽 흐름임)

• 전위 순회 : 부모 -> 왼쪽 -> 오른쪽 : 1 2 4 5 3 6 7
• 중위 순회 : 왼쪽 -> 부모 -> 오른쪽 : 4 2 5 1 6 3 7
• 후위 순회 : 왼쪽 -> 오른쪽 -> 부모 : 4 5 2 6 7 3 1

3. 정답

        <script>//전위
            function solution(v){
                let answer;
                function DFS(v){
                    if(v > 7) return;
                    else{
                        console.log(v);
                        DFS(v*2);
                        DFS(v*2+1);
                    }
                }
                DFS(v);
                return answer;
            }
            console.log(solution(1));
        </script>

        <script>//중위
            function solution(v){
                let answer;
                function DFS(v){
                    if(v > 7) return;
                    else{
                        DFS(v*2);
                        console.log(v);
                        DFS(v*2+1);
                    }
                }
                DFS(v);
                return answer;
            }
            console.log(solution(1));
        </script>

        <script>//후위
            function solution(v){
                let answer;
                function DFS(v){
                    if(v > 7) return;
                    else{
                        DFS(v*2);
                        DFS(v*2+1);
                        console.log(v);
                    }
                }
                DFS(v);
                return answer;
            }
            console.log(solution(1));
        </script>