Tree

Tree 에 대하여

트리 vs 이진 트리

모든 트리가 이진 트리인 것은 아니다.
이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 말한다.
위의 그림은 삼진 트리라고 부른다.

이진 트리 vs 이진 탐색 트리

이진 탐색 트리는 모든 노드가 다음과 같은 특정 순서를 따르는 속성이 있는 이진 트리를 일컫는다.
모든 왼쪽 자식들 <= 현재 노드 < 모든 오른쪽 자식들

위의 그림은 이진 탐색 트리가 맞다.

하지만 위의 그림은 이진 탐색 트리가 아니다. 15가 8의 왼쪽에 있기 때문이다.
이진 탐색 트리는 모든 노드에 대해서 그 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고,
오른쪽 자식들의 값은 현재 노드의 값보다 반드시 커야 한다.

완전 이진 트리 vs 전 이진 트리 vs 포화 이진 트리

완전 이진 트리 : 노드가 꽉 차 있는 이진 트리 , 마지막 단계는 꽉 차 있지 않아도 되지만
노드가 왼쪽에서 오른쪽으로 채워져야 한다.

30 번 노드를 지우거나 12 번 노드의 왼쪽에 붙여야 완전 이진 트리가 된다.

전 이진 트리 : 모든 노드의 자식이 없거나 두 개 있는 경우를 말한다.
자식이 하나만 있는 노드가 존재해선는 안된다.

30 번 노드를 지우거나 12번 노드에 자식을 하나 더 배치해야 전 이진 트리가 된다.

포화 이진 트리 : 전 이진 트리이면서 완전 이진 트리인 경우를 말한다.
위의 두 조건을 모두 만족하면 포화 이진 트리가 된다.

이진 트리 순회

node 정의

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 << ' ';
    }
}