포화이진트리(perfect binary tree), 완전이진트리

 

 

이진으로 꽉차있는 다음과 같은 트리를 말한다.

leaf node에서 오른쪽에서 부터 몇개 비면 완전이진트리라고도 한다. (때로는 포화이진트리를 완전이진트리라고 부르기도 한다.)

배열로 표현하기 좋다.

 

1베이스로 볼때.. 자식 노드는 2n, 2n+1 인덱스에 위치함을 알 수 있다.

레벨별 인덱스 위치는 1레벨이 1이고 2레벨이 2이고, 3레벨이 4이고, 4레벨이 8인것을 보아 

n레벨의 시작인덱스 위치는 $2^n$임을 알 수 있다.

 

포화이진트리코드

아래는 내가 작성한 코드이며, 배열로 포화이진트리를 받아서 preorder로 방문해준다.

이 문제의 답에 쓰이기도 했다.

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
 
//포화 이진 트리 (0-base)
struct perfect_binary_tree {
    vi v;
    int n;
    perfect_binary_tree(int* arr, int arr_size) {
        v.assign(arr, arr + arr_size);
        n = arr_size;
    }
    perfect_binary_tree(vi& v) {
        this->v = v;
        n = (int)v.size();
    }
    vi preorder() {
        vi ret;
        function<void(int)> dfs = [&](int ix) {
            ret.push_back(v[ix]);
            int l = (ix+1) * 2-1;
            int r = (ix+1) * 2 ;
            if (l < n-1) dfs(l);
            if (r < n-1) dfs(r);
        };
        dfs(0);
        return ret;
    }
};
 
int32_t main()
{
    vi v = { 1,2,3,4,5,6,7,8 };
    perfect_binary_tree t(v);
    vi p = t.preorder();
    for(int a:p)cout << a << ' ';
    return 0;
}