이진 트리의 반복적 순회

스택을 이용한 반복적 순회 구현

- 스택에 자식 노드들을 저장하고 꺼내면서 순회

- 순환 호출도 시스템 스택을 사용하고 있으므로 별도의 스택을 사용하면 순환 호출과 동일한 기능을 구현 가능

 

전체 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
} TreeNode;

#define SIZE 100
int top = -1;
TreeNode* stack[SIZE];

void push(TreeNode* p) {
	if (top < SIZE - 1)
		stack[++top] = p;
}

TreeNode* pop() {
	TreeNode* p = NULL;
	if (top >= 0) {
		p = stack[top--];
	}
	return p;
}

void inorder_iter(TreeNode* root) {
	while (1) {
		for (; root; root = root->left)
			push(root);
		root = pop();
		if (!root) break;
		printf("[%d] ", root->data);
		root = root->right;
	}
}

TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;

int main(void) {
	printf("중위 순회=");
	inorder_iter(root);
	printf("\n");

	return 0;
}

>>

- 이진 트리의 왼쪽 노드들은 NULL 노드에 도달할 때까지 스택에 추가

- NULL 노드에 도달하면 스택에서 하나씩 삭제

- 다시 이 노드의 왼쪽 노드들을 NULL 노드에 도달할 때까지 스택에 추가

- 위 과정을 공백 스택이 될 때까지 반복