Iterative Inorder Traversal

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node* left;
	struct node* right;
}Node;

Node* makeNode(int data)
{
	Node* temp;
	temp = malloc(sizeof(Node));

	temp->data = data;

	temp->left = NULL;
	temp->right = NULL;

	return temp;
}

Node* stack[100];
top = -1;

void push(Node* temp)
{
	stack[++top] = temp;
}

Node* pop()
{
	Node* temp;

	if (top < 0) return NULL; //empty 이면 -1 리턴

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

void Inorder(Node* root)
{
	Node* cur = root;
	
	while (1)
	{
		while (cur)
		// cur가 NULL이면 다시 pop
		{
			push(cur);
			cur = cur->left;
		}

		cur = pop();

		if (!cur) break; // stack이 empty

		printf("%d ", cur->data);

		cur = cur->right;
	}
	return;
}

int main()
{
	Node* root = makeNode(1);
	root->left = makeNode(2);
	root->right = makeNode(3);
	root->left->left = makeNode(4);
	root->left->right = makeNode(5);
	root->right->left = makeNode(6);
	root->right->right = makeNode(7);
	root->left->left->left = makeNode(8);

	Inorder(root);

	return 0;
}

결과

첫 과정을 제외하고는 stack에서 꺼낸 노드의 right를 기준으로만 왼쪽의 노드들을 stack에 넣는 과정들을 반복

(stack에서 꺼내진 노드들의 왼쪽 노드들은 이미 한번씩 stack에 들어감)

왼쪽 서브트리 노드들 먼저 stack -> 그 다음 자신 -> 자신 출력 후 오른쪽 서브트리의 노드들에 대하여 같은 과정 진행