신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://memostack.tistory.com/

이진 트리 Binary Tree

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

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

 

 

 

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

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

 

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

 

 

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

완전 이진 트리의 경우 자식이 모두 꽉 차있는 상태이다. (자식노드가 항상 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;
}
​

 

결과 확인

 

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기

댓글을 달아 주세요

">
  1. thumbnail
    토르
    2020.09.14 01:24

    안녕하세요

    전위 순회 그림의 8번 화살표가 맞는 건가요?

  2. thumbnail
    Favicon of https://lilly1987.tistory.com BlogIcon LillyLt

    와...코드가 더 쉽네....