문제
아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.
전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1
문제 풀이
예습이론
-
트리의 구조 분석
여기서 왼쪽자식은 부모노드x2이고, 오른쪽자식은 부모노드x2+1이다. -
이진트리 순회는 전위순회, 중위순회, 후위순회가 있고 부모를 기준으로 이름을 붙힌다. 즉, 부모가 전에있을 때는 전위순회이다.
전위순회 코드
전위순회는 부모노드 > 왼쪽 > 오른쪽 순으로 순회한다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<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>
</body>
</html>중위순회 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<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>
</body>
</html>
후위순회 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<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>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/15