inOrderTraversal(BSTNode *root)
스택 1개를 써서 중위순회로 이진 탐색 트리의 값들을 print하기
중위 순회: 왼쪽 서브트리 -> 루트 노드 방문 -> 오른쪽 서브트리
void inOrderTraversal(BSTNode *root) {
if (root == NULL) {
return ;
}
Stack *newStack;
newStack = malloc(sizeof(Stack));
if (newStack == NULL) {
return ;
}
//newStack 초기화
newStack -> top = NULL;
//루트 노드를 가리키는 cur 포인터
BSTNode *cur = root ;
while (!isEmpty(newStack) || cur != NULL) {
while (cur!=NULL) {
push(newStack, cur);
cur = cur->left ;
}
cur = pop(newStack);
printf("%d ", cur->item);
cur = cur-> right;
}
free(newStack);
}왼쪽 자식 노드로 계속 이동하면서 스택에 순서대로 Push, 왼쪽 자식이 없다면 스택에서 노드를 꺼내서 print,
그리고 꺼낸 노드의 오른쪽 자식으로 이동하면서 중위순회!
처음에는 newStack을 할당할 때 malloc(sizeof(&newStack))으로 했었는데 newStack은 이미 Stack의 구조체 포인터이기도 하고
-> malloc(sizeof(Stack))
그리고,
함수 내에서만 사용하는 지역변수인 경우에는 Malloc으로 동적할당을 해줄 필요가 굳이 없다고 한다.
참고) 함수 내에서 지역적으로 사용할 변수에서는
malloc을 사용해서 굳이 동적 메모리 할당을 해줄 필요는 없지만, 크기가 큰 배열이나 구조체는 스택에 할당할 수 있는 제한된 메모리 공간을 초과할 수 있으므로 heap 메모리를 사용하여 ->malloc()과free()를 적절하게 사용하는 것이 좋을 수 있다고 한다.
preOrderIterative(BSTNode *root):
전위순회: 루트 노드 방문 -> 왼쪽 서브트리 -> 오른쪽 서브트리
스택 1개를 써서 전위 순회로 이진 탐색 트리의 값들을 print하기
void preOrderIterative(BSTNode *root) {
if (root == NULL) {
return ;
}
Stack *newStack;
newStack = malloc(sizeof(Stack));
newStack->top = NULL;
BSTNode *cur = root;
while(!isEmpty(newStack) || cur != NULL){
while(cur!=NULL) {
push(newStack, cur);
printf("%d ", cur -> item);
cur = cur -> left;
}
cur = pop(newStack);
cur = cur -> right;
}
free(newStack);
}스택에 현재 노드를 push 하고 바로 printf 후 왼쪽 노드로 계속 이동 -> 오른쪽 노드 방문
postOrderIterative(BSTNode *root):
스택 1개를 써서 후위 순회로 이진 탐색 트리의 값들을 print하기후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트 노드로 순회한다.
void postOrderIterative(BSTNode *root) {
if (root == NULL) {
return;
}
Stack newStack;
newStack.top = NULL;
BSTNode *cur = root;
//후위 순회는 왼쪽->오른쪽->루트노드로
//탐색하기 때문에 스택에 넣을 때는
//루트 - 오른쪽 노드 - 왼쪽 노드 순으로 push
push(&newStack, cur);
push(&newStack, cur->right);
push(&newStack, cur->left);
while (!isEmpty(&newStack)) {
cur = pop(&newStack);
//해당 값이 루트 노드인 경우
//최종 출력값이 되어야하기 때문에
//반복문을 종료한다.
if (cur == root) {
printf("%d ", cur -> item);
break;
}
//스택의 맨 위의 값과 cur의 아이템이 같다면
// 방문처리 용이었기 때문에 print하고 pop
if (peek(&newStack) -> item == cur -> item) {
printf("%d ", cur->item);
pop(&newStack);
continue;
}
// 방문 추적을 위해 현재 노드를 스택에 2번 Push
if (cur->left || cur->right) {
push(&newStack, cur);
push(&newStack, cur);
//마찬가지로 오른쪽 자식부터 push
if (cur -> right) {
push(&newStack, cur->right);
}
if (cur -> left) {
push(&newStack, cur-.left);
}
//자식이 없다면 현재 노드의 값 출력
} else {
printf("%d ", cur-> item);
}
}
}노드를 두 번 스택에 푸시하여 해당 노드의 방문 여부를 추적하는게 포인트!
전위/중위 순회와 다르게 후위 순회의 경우 자식 노드를 모두 방문한 다음 부모 노드를 방문해야 한다.
그렇기 때문에 방문 처리를 통해 자식 노드의 방문 여부를 추적하고 -> 모든 자식 노드 방문 후 부모 노드를 스택에서 pop하는 방식으로 처리한다.
