2021 SISS 21기 활동/1학기 C
[HackerRank_C] Tree: Inorder, Postorder Traversal
hyerang0125
2021. 5. 11. 13:12
2021년도 1학기 5주차 과제(자료구조 복습용 tree)
1. InOrder
Tree: Inorder Traversal | HackerRank
Print the inorder traversal of a binary tree.
www.hackerrank.com
[설명]
Inorder(중위 순회)는 루트의 왼쪽 서브 트리를 방문한 뒤 루트를 방문하고 오른쪽 서브 트리를 가장 나중에 방문한다. 왼쪽 서브 트리와 오른쪽 서브 트리에 대해서 재귀적으로 이 과정을 반복한다.
풀이
void inOrder( struct node *root) {
if(root){
inOrder(root->left);
printf("%d ",root->data);
inOrder(root->right);
}
}
- root가 존재할 때, 왼쪽 서브 트리를 방문한다.
- 왼쪽 서브 트리의 방문이 끝나면 현재 데이터를 출력한다.
- 오른쪽 서브 트리를 방문한다.
실행 결과
2. Postorder
Tree: Postorder Traversal | HackerRank
Print the post order traversal of a binary tree.
www.hackerrank.com
[설명]
Postorder(후위 순회)는 먼저 루트의 왼쪽 서브 트리를 모두 방문한 뒤 오른쪽 서브 트리를 방문하고, 루트를 가장 나중에 방문한다. 왼쪽 서브 트리와 오른쪽 서브 트리에 대해서는 다시 재귀적으로 후위 순회를 수행한다.
풀이
void postOrder( struct node *root) {
if(root){
postOrder(root->left);
postOrder(root->right);
printf("%d ",root->data);
}
}
- root가 존재할 때 왼쪽 서브 트리를 호출한다.
- 왼쪽 서브 트리의 방문이 끝나면 오른쪽 서브 트리를 호출한다.
- 오른쪽 서브 트리의 방문이 끝나면 현재(root)의 데이터를 출력한다.
실행 결과