binary tree traversal(이진 트리 순회)

포인터를 사용하여 이진트리를 구성하게 되며, 포인터를 통해 왼쪽 자식 노드와 오른쪽 자식 노드를 표기하게 된다. 중앙 노드 처리부분을 어디에 놓느냐에 따라 preorder traversal, inorder traversal, postorder traversal로 나뉜다.

Preorder는 중앙 노드, 왼쪽 자식 노드, 오른쪽 자식노드 처리 순
Inorder는 왼쪽 자식 노드, 중앙 노드, 오른쪽 자식 노드 처리 순
Postorder는 왼쪽 자식 노드, 오른쪽 자식 노드, 중앙 노드 처리 순이다.

#include <iostream>

using namespace std;

int number = 15;

//하나의 노드 정보를 선언
typedef struct node* treePointer;
typedef struct node {
    int data;
    treePointer leftChild, rightChild;
}node;

//전위 순회 구현
void preorder(treePointer ptr) {
    if (ptr) {
        cout << ptr->data << ' '; // (1) 먼저 자기 자신을 처리
        preorder(ptr->leftChild); // (2) 왼쪽 자식 방문
        preorder(ptr->rightChild); //(3) 오른쪽 자식 방문
    }
}

//중위 순회 구현
void inorder(treePointer ptr) {
    if (ptr) {
        inorder(ptr->leftChild); //(1) 왼쪽 자식 방문
        cout << ptr->data << ' '; //(2) 자기 자신을 처리
        inorder(ptr->rightChild);//(3) 오른쪽 자식 방문
    }
}

//후위 순회 구현
void postorder(treePointer ptr) {
    if (ptr) {      
        postorder(ptr->leftChild); //(1) 왼쪽 자식 방문
        postorder(ptr->rightChild);//(2) 오른쪽 자식 방문
        cout << ptr->data << ' '; //(3) 자기 자신을 처리
    }
}
int main()
{
    node nodes[number + 1];

    //노드 생성
    for (int i = 0; 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]; //홀수면 오른쪽 자식이 됨
        }
    }

    //전위 진행
    printf("전위순회 방문 순서: ");
    preorder(&nodes[1]);
    printf("\n");
    printf("중위순회 방문 순서: ");
    inorder(&nodes[1]);
    printf("\n");
    printf("후위순회 방문 순서: ");
    postorder(&nodes[1]);
}

이미지 링크
자료 링크