８．３ 二分木の表現（手動編）

高さの算出が前回と違うところですね。構造体にメソッドがつけられることを忘れていたので若干処理を移動しました。あまりキレイではないですがこれくらいで。。

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

static const string ROOT = "root";
static const string INTERNAL_NODE = "internal node";
static const string LEAF = "leaf";

struct Node {
  int id;
  int parent;
  int depth;
  int height;
  int left;
  int right;

  Node() : id(), parent(-1), depth(0), height(0), left(-1), right(-1) {}

  bool hasChild() const {
    return left != -1 || right != -1; 
  }

  int getDegree() const {
    if (hasChild()) {
      if (left != -1 && right != -1) {
       return 2;
      } else {
        return 1;
      }
    } else {
      return 0;
    }
  }

  const string& getType() const {
    if (parent == -1) {
      return ROOT;
    } else if (hasChild()) {
    return INTERNAL_NODE;
    } else {
      return LEAF;
    }
  }
};

static vector<Node> TREE(25);

static void inputNode(Node& node, int id) {
  node.id = id;
  cin >> node.left >> node.right;
}

static void setDepth(vector<Node>& tree, Node& node) {
  if (node.left != -1) {
    tree[node.left].depth = node.depth + 1;
    setDepth(tree, tree[node.left]);
  }
  
  if (node.right != -1) {
    tree[node.right].depth = node.depth + 1;
    setDepth(tree, tree[node.right]);
  }
}

static int getHeight(const vector<Node>& tree, const Node& node) {
  int height = 0, leftHeight = 0, rightHeight = 0;
  if (node.hasChild()) {
    if (node.left != -1) {
      leftHeight = getHeight(tree, tree[node.left]) + 1;
    }
    if (node.right != -1) {
      rightHeight = getHeight(tree, tree[node.right]) + 1;
    }
    height = max(leftHeight, rightHeight);
  }
  return height;
}

static int getSibling(const vector<Node>& tree, const Node& node) {
  if (node.parent == -1) {
    return -1;
  } else {
    const Node& parentNode = tree[node.parent];
    if (parentNode.left == node.id) {
      return parentNode.right;
    } else {
      return parentNode.left;
    }
  }
}

static void setupTree(vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    Node& node = tree[i];
    if (node.left != -1) {
      tree[node.left].parent = node.id;
      tree[node.left].depth = node.depth + 1;
      setDepth(tree, tree[node.left]);
    }
    if (node.right != -1) {
      tree[node.right].parent = node.id;
      tree[node.right].depth = node.depth + 1;
      setDepth(tree, tree[node.right]);
    }
    node.height = getHeight(tree, node);
  }
}

static void printTree(const vector<Node>& tree, int num) {
  int depth = 0, sibling = 0;
  for (int i = 0; i < num; i++) {
    sibling = getSibling(tree, tree[i]);
    const string& type = tree[i].getType();
    printf("node %d: parent = %d, sibling = %d, degree = %d", i, tree[i].parent, sibling, tree[i].getDegree());
    printf(", depth = %d, height = %d, %s\n", tree[i].depth, tree[i].height, type.c_str());
  }
}

int main() {
  int n;
  cin >> n;

  int id;
  for (int i = 0; i < n; i++) {
    cin >> id;
    inputNode(TREE[id], id);
  }
  
  setupTree(TREE, n);
  printTree(TREE, n);

  return 0;
}