【AOJ ALDS1_9】A: Heaps - Complete Binary Tree

問題

ヒープ 完全二分木 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• 完全二分木とは, すべての葉が同じ深さであり内部節点の次数が2であるような二分木である.
• 節点番号がiであるとき, 親はi/2, 左の子ノードは2i, 右の子ノードは2i+1で求めることができる.

コード

#include<iostream>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

signed main(){
  int h;
  int A[251];
  cin >> h;
  for(int i = 1 ; i <= h ; i++){
    cin >> A[i];
  }

  for(int i = 1 ; i <= h ; i++){
    cout << "node " << i << ": key = " << A[i] << ", ";
    if(i/2 >= 1) cout << "parent key = " << A[i/2] <<  ", ";
    if(2 * i <= h) cout << "left key = " << A[2 * i] << ", ";
    if(2 * i + 1 <= h) cout << "right key = " << A[2 * i + 1] << ", ";
    cout << "\n";
  }
}