[C++] 이진트리 순회

순회

• 이진 트리에서 데이터를 탐색하는 방법은 크게 세 가지 방법이 있다.
  • 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)

전위 순회

• 전위 순회는 Root를 제일 먼저 처리합니다.
• 순서
  • Root (자기 자신)
  • 왼쪽 자식
  • 오른쪽 자식
• 위의 트리에서 전위 순회로 순회를 한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서입니다.

중위 순회

• 중위 순회는 Root를 가운데 순번에서 처리합니다.
• 순서
  • 왼쪽 자식
  • Root (자기 자신)
  • 오른쪽 자식
• 위의 트리에서 중위 순회로 순회를 한다면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 순서입니다.

후위 순회

• 후위 순회는 Root를 가장 마지막에서 처리합니다.
• 순서
  • 왼쪽 자식
  • 오른쪽 자식
  • Root (자기 자신)
• 위의 트리에서 후위 순회로 순회를 한다면 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1 순서입니다.

코드

#include <iostream>

using namespace std;

const int number = 7;

typedef struct node* treePointer;
typedef struct node {
    int data;
    treePointer leftChild, rightChild;
} node;

// 전위 순회 구현
void preorder(treePointer ptr) {
    if (ptr) {
        cout << ptr->data << " ";
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
    }
}

// 중위 순회 구현
void inorder(treePointer ptr) {
    if (ptr) {
        inorder(ptr->leftChild);
        cout << ptr->data << " ";
        inorder(ptr->rightChild);
    }
}

// 후위 순회 구현
void postorder(treePointer ptr) {
    if (ptr) {
        postorder(ptr->leftChild);
        postorder(ptr->rightChild);
        cout << ptr->data << " ";
    }
}

int main(void) {
    node nodes[number + 1];

    //초기화
    for (int i = 1; i <= number; i++) {
        nodes[i].data = i;
        nodes[i].leftChild = NULL;
        nodes[i].rightChild = NULL;
    }

    for (int i = 1; i <= number; i++) {
        if (i % 2 == 0)
            nodes[i / 2].leftChild = &nodes[i];
        else
            nodes[i / 2].rightChild = &nodes[i];
    }

    preorder(&nodes[1]);
    cout << endl;
    inorder(&nodes[1]);
    cout << endl;
    postorder(&nodes[1]);
    cout << endl;

    return 0;
}