트리의 순회 방법

트리의 순회 방법

1. 전위 순회 (pre-order traverse)
2. 중위 순회 (in-order traverse)
3. 후위 순회 (post-order traverse)
4. 레벨 순회 (level-order traverse)

1.전위 순회

root 방문

left subtree 방문 (leaf가 나올 때 까지)

right subtree 방문 (leaf가 나올 때 까지)

       

         A->B->C->D->E->F->G->H->I->J->K

전위 순회 CODE

[-] Collapse

void pre_order(Node* root) {
    cout << root->val << endl;
    if (root->left != NULL)
        pre_order(root->left);
    if (root->right != NULL)
        pre_order(root->right);
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


2.중위 순회

left subtree 방문 (left child가 없을때 까지 재귀 호출)
root 방문
right subtree 방문


         D->C->E->B->F->A->I->H->G->J->K


중위 순회 CODE

[-] Collapse

void in_order(Node* root) {
    if (root->left != NULL) {
        in_order(root->left);
        cout << root->val << endl;
        in_order(root->right);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


3.후위 순회

let subtree 방문
right subtree 방문
root 방문


         D->E->C->F->B->I->H->K->J->G->A


후위 순회 CODE


[-] Collapse

void post_order(Node* root) {
    if (root->left != NULL) {
        post_order(root->left);
        post_order(root->right);
        cout << root->val << endl;
    }
}


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


4.레벨 순회

BFS와 같다. (ROOT와 거리가 가까운 노드부터 방문)



         A->B->G->C->F->H->J->D->E->I->K


레벨 순회 CODE

[-] Collapse

queue<Node*> q;
void level_order(Node* root) {
    if (q.empty()) return;

    q.pop();

    cout << root->val << endl;
    if (root->left != NULL)
        q.push(root->left);

    if (root->right != NULL)
        q.push(root->right);

    level_order(q.front());
}