[자료구조] DFS: Preorder Traversal

노드 접근 방식

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

1. Inorder Traversal
2. Postorder Traversal
   3. Preorder Traversal

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

Level Order Traversal

---

Preorder Traversal

• 가운데 -> 왼쪽 -> 오른쪽
• 적용 사례) Prefix expression evaluation (In stack-like(reverse) order using a stack)

1. Prefix expression evaluation

알고리즘)
1. 포인터 P를 문자열의 끝에 놓기
2. P 위치에서 문자열일 때, stack에 push
3. P 위치에서 operator(연산자)일 때,
3-1. stack에서 2개의 요소를 pop
3-2. 2개의 요소와 연산자 함께 연산을 진행하고 해당 결과값을 stack에 push
4. P 위치를 1개씩 감소시키면서, 과정 2로 이동
5. 결과값을 stack에 push

• postorder의 인덱스를 reverse하게 진행하는 거랑 똑같다..

예시: Expression: "+9*26"

스캔된 문자	스택(앞-뒤)	설명
6	6	6 스택에 넣기
2	6 2	2 스택에 넣기
*	12	*는 연산자이므로, 6*2 = 12 스택에 넣기
9	12 9	9 스택에 넣기
+	21	+는 연산자이므로, 12+9 = 21 스택에 넣기

=> 결과값: 21

// JavaScript
function evaluatePostfix(exp)
{
        let stack=[];
          
        // 제공된 문자열을 한 글자씩 살펴보기
        for(let i=exp.length - 1;i>=0;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();
              	// == let val1 = stack[stack.length - 1] 
                  
                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(); // 결과값 반환 
  		// == stack[stack.length - 1];
}
 
let exp="+9*26";
evaluatePostfix(exp); // 21

Time Complexity: O(N)
Auxiliary Space: O(N)

2. Preorder Traversal in a Binary Tree

class Node {
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function preorderTraversal(node)
{
    if (node === null)
        return;

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

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

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

const 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);
preorderTraversal(root);

+) 참고 자료:

• https://www.geeksforgeeks.org/evaluation-prefix-expressions/?ref=gcse_outind
• https://www.geeksforgeeks.org/preorder-traversal-of-binary-tree/?ref=gcse_outind