알고리즘 :: 이진트리와 순회 전위순회(preorder), 중위 순회(inorder), 후위 순회(postorder) C/C++ 구현

이진 트리 Binary Tree

부모와 자식으로 나눠져있는 트리 그래프

자식은 왼쪽자식(left child), 오른쪽 자식(right child)로 나눠진다.

 

 

 

이진트리는 분할정복 탐색 알고리즘으로,

빠른속도로 탐색이 가능하다는 장점이 있다.

 

힙정렬의 경우 이진트리를 이용해서 정렬을 수행한다.

 

힙정렬

2018/04/29 - [Algorithm] - 자료구조 :: 힙 정렬 Heap sort (c/c++ 구현)

자료구조 :: 힙 정렬 Heap sort (c/c++ 구현)

 

이진트리에도 종류가 있는데,

완전 이진 트리의 경우 자식이 모두 꽉 차있는 상태이다. (자식노드가 항상 2개)

이 경우는 구현을 할때, 굳이 left, right로 나눌필요가 없다.

 

 

하지만, 위의 경우는 (완전이진트리가 아닌경우)

left와 right로 구분이 되기 때문에,

구현을 할때, left 노드 정보와 right 노드 정보를

포인터를 이용해서 가리킨다.

 

 

순회 Traversal

이진트리를 이용하여 순회(Traversal)을 할 수 있다.

순회의종류에는 3가지가 존재한다.

1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

전위 순회 Preorder Traversal

root -> left -> right

부모노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

 

8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

중위 순회 Inorder Traversal

left -> root -> right

왼쪽 자식 노드  -> 부모노드 -> 오른쪽 자식 노드

 

 

8 9 4 10 11 5 2 12 13 6 14 15 7 3 1

후위 순회 Postorder Traversal

left -> right -> root

왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모노드 

 

코드 구현

#include <iostream>

using namespace std;

int number = 15;

typedef struct node *nodePointer;
typedef struct node{
    int data;
    nodePointer left, right;
} node;

// 전위
void preorder(nodePointer pointer){
    if(pointer){
        // pointer가 null이 아니라면
        cout << pointer->data << ' ';
        preorder(pointer->left);
        preorder(pointer->right);
    }
}

// 중위
void inorder(nodePointer pointer){
    if(pointer){
        // pointer가 null이 아니라면
        inorder(pointer->left);
        cout << pointer->data << ' ';
        inorder(pointer->right);
    }
}

// 후위
void postorder(nodePointer pointer){
    if(pointer){
        // pointer가 null이 아니라면
        postorder(pointer->left);
        postorder(pointer->right);
        cout << pointer->data << ' ';
    }
}

int main(void){
    node nodes[number+1];
    // 초기화
    for(int i=1; i<= number; i++){
        nodes[i].data = i;
        nodes[i].left = NULL;
        nodes[i].right = NULL;
    }
    
    for(int i=2; i<=number; i++){
        if(i%2==0){
            nodes[i/2].left = &nodes[i];
        }else{
            nodes[i/2].right = &nodes[i];
        }
    }
    
    preorder(&nodes[1]);
    cout << endl;
    inorder(&nodes[1]);
    cout << endl;
    postorder(&nodes[1]);
    cout << endl;
    
    return 0;
}
​

 

결과 확인