[Jungle][TIL] 240419 Binary Search Trees(BST) - (3)

postOrderIterative(BSTNode *root)
후위 순회로 이진 탐색 트리 값들을 Print하는 함수

void postOrderIterative(BSTNode *root) {
	
    Stack s1;
    s1.top = NULL;
    
    Stack s2;
    s2.top = NULL;
    
    BSTNode *cur = root;
    
    push(&s1, root);
    
    while (cur!= NULL || !isEmpty(&s1)) {
    	cur = pop(&s1);
        if (cur->left != NULL) {
        	push(&s1, cur->left);
        }
        
        if (cur->right != NULL){
        	push(&s2, cur->right);
        }
    
    	push(&s2, cur);
        cur = NULL;
    }

	while (!isEmpty(&s2)) {
    	cur = pop(&s2);
        printf("%d ", cur->item);
    }

}

S2 스택: 실제 후위 순서로 방문된 노드를 저장하기 위한 스택
S1 스택을 활용해서 현재 처리 중인 노드 저장하고 있다. 왼쪽 자식 -> 오른쪽 자식 순으로 처리