Week-05

Binary Search Tree - 4번)

Stack 1개를 이용한 Post-Order traversal 구현

Implement By Recursive

Post-Order Traversal

• 왼쪽 자식 Traversal
• 오른쪽 자식 Traversal
• 자기 자신 Order
  
  

구현 아이디어

Stack->Top()의 행동 제어
Case 1. Push(Left->Child)
Case 2. Push(Right->child)
Case 3. Pop() => (Order)


이전에 Pop 되었던 Value를 기억하여 행동 판단.
이전 Pop_Value(이하 visit)


Rule 1
visit == top()->right
=> Pop()
Rule 2
visit != top()->left
=> Loop왼쪽 최하단까지(push(left))
Rule 3
visit == top()->left
=> push(right)

Summary

오른쪽 검사(같으면 Pop, 다르면 왼쪽검사)
왼쪽 검사(같으면 오른쪽 Push, 다르면 왼쪽 최하단까지 Push)

Example Visualization

Implementation Using Stack(Iterative Post-Order Traversal)

void postOrderIterativeS1(BSTNode *root)
{
	Stack s;
	s.top = NULL;
	push(&s, root);
	int visit = root->item;
	while(!isEmpty(&s)){
		if(peek(&s)->right != NULL && peek(&s)->right->item == visit){
			BSTNode* cur = pop(&s);
			visit = cur->item;
			printf("%i ", cur->item);
			continue;
		}
		while(peek(&s)->left != NULL && peek(&s)->left->item != visit){
			push(&s, peek(&s)->left);
		}
		if(peek(&s)->right == NULL){
			BSTNode* cur = pop(&s); 
			visit = cur->item;
			printf("%i ", cur->item);
		}
		else{
			push(&s, peek(&s)->right);
		}
	}
}