이진트리와 순회

이진트리는 모든 노드가 두개의 서브트리를 가지고 있는 트리를 이진트리라고 한다. 서브트리는 공집합일 수 있다.

따라서 이진트리의 노드에는 최대 두개의 자식노드를 가질 수 있다. 또한 서브 트리간에 순서가 존재한다.

정확히 설명하자면

1. 공집합이거나
2. 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한집합으로 정의된다. 이진트리의 서브 트리들은 모두 이진트리여야한다.

이처럼 이진트리는 재귀적으로 정의되기 때문에 재귀 알고리즘을 쓰는 것이 여러모로 편리하다

이진트리의 종류

1. 포화 이진트리
   트리의 각 레벨에 노드가 꽉 차 있는 트리, 높이를 k라 한다면 등비수열 합 공식에 의해 노드 수는 2^k -1개
2. 완전 이진트리
   트리의 높이가 k일 때 k-1까지는 노드가 모두 채워져있고 마지막 레벨에서는 노드들이 왼쪽부터 채워져 있는 트리. 배열로 이용하기 편하다.

이런 트리로 순회를 연습해보자.

 

트리를 구현한 코드

struct TreeNode{
    int value;
    TreeNode * left = nullptr;
    TreeNode * right = nullptr;
};

int main(){

    TreeNode n11 = {11, nullptr, nullptr};
    TreeNode n10 = {10, nullptr, nullptr};
    TreeNode n9 = {9, nullptr, nullptr};
    TreeNode n8 = {8, &n11, nullptr};
    TreeNode n7 = {7, nullptr, nullptr};
    TreeNode n6 = {6, &n9, &n10};
    TreeNode n5 = {5, nullptr, nullptr};
    TreeNode n4 = {4, &n7, &n8};
    TreeNode n3 = {3, nullptr, &n6};
    TreeNode n2 = {2, &n4, &n5};
    TreeNode n1 = {1, &n2, &n3};
    

    return 0;
}

전위 순회 (Preorder Traversal) : 루트노드 - 왼쪽 서브트리 - 오른쪽 서브트리

중위 순회(Inorder Traversal) : 왼쪽 서브트리 - 루트노드 - 오른쪽 서브트리

후위 순회(Postorder Traversal) : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트노드

void preorder(TreeNode *root){
    if(root){
        std::cout << root->value << " ";
        preorder(root->left);
        preorder(root->right);
    }
}
void inorder(TreeNode *root){
    if(root){
        inorder(root->left);
        std::cout << root->value << " ";
        inorder(root->right);
    }
}

void postorder(TreeNode *root){
    if(root){
        postorder(root->left);
        postorder(root->right);
        std::cout << root->value << " ";
    }
}

 

자식노드 모두 처리하고 부모노드를 처리애야 한다면 후위순회를 해야한다.

부모노드를 먼저 처리하고 자식노드를 처리해야한다면 전위순회를 해야한다.

 

노드 수, 리프 노드 수, 높이 세기

int get_node_count(TreeNode *root){
    int count = 0;
    if(root){
        count = 1 + get_node_count(root->left) + get_node_count(root->right);
    }
    return count;
}

int get_leaf_count(TreeNode *root){
    int count = 0;
    if(root) {
        if (!root->left and !root->right)
            return 1;
        else
            count = get_leaf_count(root->left) + get_leaf_count(root->right);
    }
    return count;
}
int get_height(TreeNode *root){
    int height = 0;
    if(root){
        height = 1 + std::max(get_height(root->left),get_height(root->right));
    }
    return height;
}