후위 순회 구현

트리에 대한 기본 개념(자식, 루트 노드 등)을 알고 있다는 것을 전제로 합니다. + 재귀함수

 

 

후위 순회 (Post Order)는 트리를 순회하는 방법 중 하나로,

[왼쪽 자식 -> 오른쪽 자식 -> 루트 노드] 순서대로 순회한다.

트리 구조

[ D -> E -> B -> F -> G -> C -> A ]

이 순서로 순회를 한다.

---

이를 C언어로 구현하면 다음과 같다.

#include <stdio.h>
 
typedef struct TreeNode
{
    int data;
    struct TreeNode *left, *right;
} treenode;
 
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;
//        15
//      /   \
//     4      20
//    /     /   \
//  1     16      25
 
void postorder(treenode* node){
    if(node != NULL){
        postorder(node->left);
        postorder(node->right);
        printf("%d ", node->data);
    }
    return;
}
 
int main(){
    postorder(root);
}

[ 1 4 16 25 20 15 ] 순서대로 출력이 된다.