10.2 完全二分木

ヒープ編に突入。今回は問題文通りの実装です。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;
}