[자료구조] DFS: Postorder Traversal

혜써클이 떴습니다☀️·2024년 11월 5일

자료구조 및 알고리즘

목록 보기

3/8

노드 접근 방식

1. Deth-First(Traversal/Search)(DFS: 깊이 우선 탐색)

Inorder Traversal
2. Postorder Traversal
Preorder Traversal

2. Breadth-First(Traversal/Search)(BFS: 너비 우선 탐색)

Level Order Traversal

Postorder Traversal

1. Postorder Traversal of Binary Tree

// 이진 트리 노드 구조
class Node {
  constructor(v) {
    this.data = v;
    this.left = null;
    this.right = null;
  }
}

function printPostorder(node) {
  if (node == null) {
    return;
  }

  // 왼쪽으로 이동
  printPostorder(node.left);

  // 오른쪽으로 이동
  printPostorder(node.right);

  // 노드값 출력
  console.log(node.data + " ");
}

function main() {
  let root = new Node(1);
  root.left = new Node(2);
  root.right = new Node(3);
  root.left.left = new Node(4);
  root.left.right = new Node(5);
  root.right.right = new Node(6);

  // Function call
  console.log("Postorder traversal of binary tree is: \n");
  printPostorder(root);
}

main();

2. 적용사례: Postfix expression(접미사 표현식)

알고리즘)
1. stack 필요
2. 숫자일 때는 stack에 push
3-1. 연산자일 때는 stack의 최상단 2개의 요소를 pop
3-2. 연산자를 적용한 결과값을 다시 stack에 push

// JavaScript
function evaluatePostfix(exp)
{
        let stack=[];
          
        // 제공된 문자열을 한 글자씩 살펴보기
        for(let i=0;i<exp.length;i++){
            let c=exp[i];
              
            // 스캔한 문자가 숫자일 때,stack에 push
            if(! isNaN( parseInt(c) ))
            	stack.push(c.charCodeAt(0) - '0'.charCodeAt(0));
              
            // 스캔한 문자가 연산자일 때, stack에서 2개 요소 pop
            // 그리고 stack에 push
            else{
                let val1 = stack.pop();
                let val2 = stack.pop();
                  
                switch(c){
                    case '+':
                    stack.push(val2+val1);
                    break;
                      
                    case '-':
                    stack.push(val2- val1);
                    break;
                      
                    case '/':
                    stack.push(val2/val1);
                    break;
                      
                    case '*':
                    stack.push(val2*val1);
                    break;
              }
            }
        }
        return stack.pop(); // 결과값 반환 
}
 
// Driver program to test above functions
let exp="231*+9-";
evaluatePostfix(exp); // -4