８．４ 木の巡回（手動編）

詳細は端折りますが、いろいろと難しく考えすぎて失敗しました。こんなシンプルな方法で巡回になるんですね。。

#include <iostream>
#include <vector>

using namespace std;

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

  Node() : id(), parent(-1), left(-1), right(-1) {}
  };

static vector<Node> TREE(25);

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

static const Node& getRoot(const vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    if (tree[i].parent == -1) {
      return tree[i];
    } 
  }
}

static void getNextPreorder(const vector<Node>& tree, const Node& node) {
  if (node.id == -1) {
    return;
  }

  cout << " " << node.id;
  
  if (node.left != -1) {
    getNextPreorder(tree, tree[node.left]);
  }

  if (node.right != -1) {
    getNextPreorder(tree, tree[node.right]);
  }
}

static void preorderTreeWalk(const vector<Node>& tree, const Node& root) {
  cout << "Preorder" << endl;
  getNextPreorder(tree, root);
  cout << endl;
}

static void getNextInorder(const vector<Node>& tree, const Node& node) {
  if (node.id == -1) {
    return;
  }
  
  if (node.left != -1) {
    getNextInorder(tree, tree[node.left]);
  }

  cout << " " << node.id;

  if (node.right != -1) {
    getNextInorder(tree, tree[node.right]);
  }
}

static void inorderTreeWalk(const vector<Node>& tree, const Node& root) {
  cout << "Inorder" << endl;
  getNextInorder(tree, root);
  cout << endl;
}

static void getNextPostorder(const vector<Node>& tree, const Node& node) {
  if (node.id == -1) {
    return;
  }
  
  if (node.left != -1) {
    getNextPostorder(tree, tree[node.left]);
  }

  if (node.right != -1) {
    getNextPostorder(tree, tree[node.right]);
  }

  cout << " " << node.id;
}

static void postorderTreeWalk(const vector<Node>& tree, const Node& root) {
  cout << "Postorder" << endl;
  getNextPostorder(tree, root);
  cout << endl;
}

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;
    }
    if (node.right != -1) {
      tree[node.right].parent = node.id;
    }
  }
}

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

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

  setupTree(TREE, n);
  const Node root = getRoot(TREE, n);

  preorderTreeWalk(TREE, root);
  inorderTreeWalk(TREE, root);
  postorderTreeWalk(TREE, root);

  return 0;
}