이진 트리_반복 중위 순회(Iterative Inorder Traversal)

stack을 이용하여 비순환적으로 Inorder Traversal 구현

[순회 순서]

1. left subtree

2. root node

3. right subtree

[소스코드]

Node* stack[MAX_STACK_SIZE];
int top;

void push(Node* node) {
	if(top >= MAX_STACK_SIZE-1) {
		return;
	}

	top++;
	stack[top] = node;
}

Node* pop() {
	Node* node = NULL;
	if(top == -1) {
		return node;
	}

	node = stack[top];
	top--;
	return node;
}

void iter_inorder(Node* root) {
	Node* ptr;
	top = -1;

	ptr = root;
	while(1) {
		while(ptr != NULL) {
			push(ptr);
			ptr = ptr->left_child;
		}

		ptr = pop();
		if(ptr == NULL) break;
		printf("%d ", ptr->data);
		ptr = ptr->right_child;
	}
}

[결과]