Inorder Traversal 을 반복문으로 코딩하는 방법

목표 : Stack을 이용하여 중위순회를 반복문으로 구현할 수 있다.

일반적으로 순회는 재귀를 이용하여 구현하는데 반복문으로 구현하는 것이 목표다.

중위 순회의 순서는 다음과 같다.

1. left SubTree

2. root Node

3. right SubTree

#include <iostream>
#include <stack>
using namespace std;
struct Node {
    Node* left;
    Node* right;
    int value;
};
stack <Node *> Nodestack;

void push(Node* node) {
    Nodestack.push(node);
}

Node* pop() {
    Node* node = Nodestack.top();
    Nodestack.pop();
    return node;
}

void iterativeInorderTrav(Node* root) {
    Node *ptr;
    ptr = root;
    while(1) {
        while(ptr != NULL) {
            Nodestack.push(ptr);
            ptr = ptr->left;
        }
        if(Nodestack.empty())
            break;
        ptr = Nodestack.top();
        Nodestack.pop();
        printf("%d ",ptr->value);
        ptr = ptr->right;
    }
}