stack으로 구현한 binary tree의 순회 구조

이진 트리의 순회 구조는 크게 3가지가 존재합니다
preorder, inorder, postorder입니다.

먼저 왼쪽으로 이동 후 방문 후 다시 오른쪽을 preorder,
왼쪽으로 이동 후 오른쪽으로 다시 가서 읽는 것을 inder,
그리고 오른쪽으로 간 뒤 읽고 왼쪽으로 가는 것은 postorder라고 합니다.

stack과 queue를 사용하지 않아도, 물론 구현할 수 있다.
해당 코드들은 재귀형식으로 구현 가능하다.

이번에는 stack을 활용하여 작성하여 보겠습니다.

먼저 stack을 사용하는 건 postorder과 inorder이 있습니다.

먼저 inorder을 작성해보겠습니다

typedef struct Node{ //노드 하나를 선언합니다
  int data;
  struct Node* left; // 좌하행 간선입니다
  struct Node* right; // 우하행 간선입니다
};
struct Node* createNode(int data){ // 노드를 생성하는 함수입니다
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // malloc을 이용해 메모리를 할당합니다
  newNode-> data = data; // 인자에 들어가는 값을 데이터로 사용합니다
  newNode -> left = NULL; // 좌하행 간선을 NULL로 연결시킵니다
  newNode -> right = NULL; // 우하행 간선을 NULL로 연결시킵니다
  return newNode;
  
}
void inorderTraversal(struct Node* root){ // 코드를 출력하는 함수입니다
  if(root == NULL){
    return; // 스택이 비어있다면 리턴합니다
  }
  struct Node* stack[100]; // 스택을 선언합니다.
  int top = -1; // 스택을 초기화합니다
  struct Node* current = root; // 스택의 첫번째 값
  while (current != NULL || top >= 0) { current가 널이 아닐때까지
      while (current != NULL) { // 현재가 null일 때까지
          stack[++top] = current; // current를 스택에 집어넣음
          current = current->left; // left로 집어넣음
      }
      current = stack[top--]; // 이전 스택에 있는 값
      printf("%d ", current->data); // 값을 출력함
      current = current->right; // 
  }
}


int main(void) {
  struct Node* root = createNode(1);
  root-> left = createNode(2);
  root-> right = createNode(3);
  root -> left -> left = createNode(4);
  root->left->right =createNode(5);
  root -> right ->left = createNode(6);
  root -> right -> right = createNode(7);
  inorderTraversal(root);
  
  
  return 0;
}

위의 코드를 분석해 보겠습니다.
코드는 stack을 활용한 것으로, current에 하나씩 저장합니다. 일단 left를 전부 이동하여 저장 후 없으면 right, 그리고 다시 이전 스택에 있는 값을 불러오도록 합니다. 그래서 inorder을 만들었습니다. 그렇다면 postorder는 어떻게 만들까요?
struct 선언까지는 앞과 같습니다.

void postorderTraversal(struct Node* root){ // 후위 순회를 하는 알고리즘
  if(root == NULL){ 
    return;
  }
  struct Node* stack[100]; // 스택을 정의
  int top = -1; // 초기화
  struct Node* lastVisited = NULL; // 이전 값을 저장할 배열을 정의
  struct Node* current = root; // 값을 넣을 배열 포인터선언
  while(current != NULL || top >=0){ // 반복
    while(current != NULL){ // 현재값이 널이 아닐때까지 반복
      stack[++top] = current; // 스택에 값을 저장
      current = current -> left; // 값을 왼쪽으로 이동
      
    }
    struct Node* peekNode = stack[top]; // pop되는 값을 저장함
    if(peekNode -> right != NULL && lastVisited != peekNode -> right){ // 우하향 노드가 널이고 이전에 방문한 노드에 right가 있을때
      current = peekNode-> right; // right로 향함
    }
    else{
      printf("%d ", peekNode->data); // data를 찍음
      lastVisited = stack[top--]; // 이전 값으로 
    }
  }

이 코드를 해석하겠습니다. tree의 postorder를 순회하는 코드입니다.
스택에서 null일때까지 쭉 갑니다. 그리고 pop된 값을 출력하도록 포인터를 작성해줍니다.
그 포인터의 right가 널이고 전에 방문한 값이 이전 값이 right로 향하는 간선이 null이 아니라면 right로 향합니다.
그리고 data를 찍습니다.
그리고 이전 값으로 이동합니다.