[자료구조]C++ 이진트리 순회하기

 

 

위와같이 값이 알파벳으로 되어있는 트리를 만들 것이다. (출처 : 백준 1991번 트리순회)

 

1.노드 생성

 

이진트리를 구성하기 위해 node라는 구조체를 만든다.

 

struct node {
    node* left;
    node* right;
    char value;
};

 

구조체 안에는 위와 같이 실제값, 왼쪽노드를 가리키는 left포인터, 오른쪽 자식을 가리키는 right포인터로 구성된다.

 

2.트리 생성

 

새로운 node를 생성 할 때에는

 

node *tree;
tree = (node*)malloc(sizeof(node));
tree->value = 'A';
tree->left = NULL;
tree->right = NULL;

 

위와같이 포인터로 생성하고 동적할당을 해준다.

 

해당되는 value를 넣어주고 왼쪽자식이나 오른쪽 자식이 없으면 NULL값을 넣어주고,

 

있는 경우에는 해당 노드를 가리키면 된다.

 

모든 노드는 포인터로 생성하며 포인터이기 때문에 value,left,right를 참조 할때에는

 

tree->value와 같이 -> 기호를 사용하여 참조한다.

 

3.순회

 

순회에는 다음과 같이 세가지 방법이 있다. 루트노드를 기준으로 구분한다.

 

- 전위순회(preorder traversal)

 

 루트노드를 방문하기 전에 left child가 있으면 먼저 방문하고 해당 루트노드순회 후에 right child를 방문하는 순서이다.

 

- 중위순회(inorder traversal)

 

 루트노드를 우선 방문한 후에 left child가 있으면 방문하고 후에 right child를 방문하는 순서이다.

 

- 후위순회(postorder traversal)

 

 루트노드를 방문하기 전에 left child가 있으면 먼저 방문하고 right child가 있으면 방문하고 마지막으로 해당 루트 노드를 순회한다.

 

void preorder(node *n) {
    cout << n->value;
    if(n->left!=NULL)
        preorder(n->left);
    if (n->right != NULL)
        preorder(n->right);
}
void inorder(node *n) {
    if (n->left != NULL)
        inorder(n->left);
    cout << n->value;
    if (n->right != NULL)
        inorder(n->right);
}
void postorder(node *n) {
    if (n->left != NULL)
        postorder(n->left);
    if (n->right != NULL)
        postorder(n->right);
    cout << n->value;
}

 

소스코드로는 위와같이 구현할 수 있다. 

 

출력 순서만 바꾸어주면 쉽게 구현이 가능하다.

 

맨 위와 같은 그래프에서 출력하면

 

preorder :  ABDCEFG 

inorder :    DBAECFG 

postorder:  DBEGFCA

 

이렇게 출력이 된다.