ヒープ編に突入。今回は問題文通りの実装です。parent, left, right が単純な計算で決定するのが面白いですね。なお、解説の実装では、木の実装が int の配列になっており、自分の実装は無駄な箇所が多々あります。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Node {
int key;
Node* parent;
Node* left;
Node* right;
Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};
static vector<Node> tree;
int main() {
int h;
cin >> h;
tree.resize(h + 1);
int k;
for (int i = 1; i < tree.size(); i++) {
cin >> k;
tree[i].key = k;
}
int parent, left, right;
for (int i = 1; i < tree.size(); i++) {
parent = i / 2;
if (parent != 0) {
tree[i].parent = &tree[parent];
}
left = 2 * i;
if (left < tree.size()) {
tree[i].left = &tree[left];
}
right = 2 * i + 1;
if (right < tree.size()) {
tree[i].right = &tree[right];
}
}
for (int i = 1; i < tree.size(); i++) {
auto& node = tree[i];
printf("node %d: key = %d, ", i, node.key);
if (node.parent) {
printf("parent key = %d, ", node.parent->key);
}
if (node.left) {
printf("left key = %d, ", node.left->key);
}
if (node.right) {
printf("right key = %d, ", node.right->key);
}
printf("\n");
}
return 0;
}